فريدة من نوعها 1 في 3 جلست

Question

لنفترض أن لدي صيغة CNF مع بنود الحجم 2 و 3. لديها مهمة مرضية فريدة من نوعها.

أعرف قيمة كل بت من المهمة الفريدة لأنها مصنوعة من دائرة الضرب الثنائية حيث تضاعفت اثنين من الأرقام الأولية A و B بحيث يكون A * B= S ES رقم Semiprime. أضفت الظروف التي!= 1، b!= 1 و <= b، ثم أضفت قيمة S إلى الصيغة تأكد من أن المهمة فريدة من نوعها. الطريقة الوحيدة لإرضاء الصيغة هي وضع قيم A و B بالترتيب الصحيح في أجزاء الإدخال.

عدد الأدوات الحرفية الحقيقية في كل جملة هو إما 1 أو 2 أو 3. لأنني أعرف قيمة كل بت، يمكنني أن أقول بالضبط ما هي الحرفية صحيحة في كل بند، وحسبها. على سبيل المثال، أعرف أن البنود راضية بالضبط 1 حرفي. وهذا حرفي جزء منطقيا من الحل الفريد.

سؤالي بسيط: إذا قمت بإزالة جميع البنود بأكثر من 1 حرفي حقيقي، فهل ستظل المهمة بالضرورة فريدة من نوعها؟

بمعنى آخر، إذا كنت أرغب في كتابة دليل على الدقة (من المحتمل أن يكون طويلا بشكل كبير) لإظهار أن الحل فريد من نوعه (مشكلة حل أخرى، في CO-NP)، هل يمكنني كتابة ذلك باستخدام البنود فقط مع 1 صحيح حرفي؟

بشكل حدسي، أعتقد ذلك، لكنني غير قادر على الدفاع عن وجهة نظري، حتى عند التفكير في ما يعادل 2SAT.

Answer 1

النظر في CNF التالية: $$ (a \ lor \ lnot b) \ lnot (\ lnot a \ lor b) \ land (a \ lor b). $ لديها مهمة مرضية فريدة من نوعها، $ a= b=top $ ، والتي ترضي الفقرة الأخيرة مرتين.ومع ذلك، إذا قمت بإزالة البند الأخير، فأنت تحصل على مهمة مرضية أخرى، $ a= b=bot $ .