Ko'ngilsiz yadro - Unsatisfiable core

Yilda matematik mantiq, berilgan qoniqarsiz Mantiqiy taklif formulasi yilda konjunktiv normal shakl, birikmasi hanuzgacha ma'qul kelmaydigan gaplarning quyi qismiga an deyiladi qoniqarsiz yadro asl formuladan.

Ko'pchilik SAT echimlari ishlab chiqarishi mumkin qaror grafigi bu asl muammoning to'yintirilmasligini isbotlaydi. Buni kichikroq to'yintirilmaydigan yadro hosil qilish uchun tahlil qilish mumkin.

To'yinmaydigan yadro a deb nomlanadi minimal qondirilmaydigan yadro, agar uning har bir to'g'ri to'plami (har qanday o'zboshimchalik bilan band yoki bandlarni olib tashlashga imkon beradigan) qoniqarli bo'lsa. Shunday qilib, bunday yadro a mahalliy minimal, albatta, global emas. Minimal to'yintirilmagan yadrolarni hisoblashning bir necha amaliy usullari mavjud.[1][2]

A minimal qondirilmaydigan yadro hali ham qoniqarsiz bo'lishi uchun zarur bo'lgan asl bandlarning eng kichik sonini o'z ichiga oladi. Minimal yadroni hisoblashning amaliy algoritmlari ma'lum emas.[3] Terminologiyaga e'tibor bering: aksincha minimal qondirilmaydigan yadro oson echimi bo'lgan mahalliy muammo edi minimal qondirilmaydigan yadro ma'lum bo'lgan oson echimi bo'lmagan global muammo.

Adabiyotlar

  1. ^ N. Dershovits, Z. Xanna va A. Nadel, Minimal qoniqarsiz yadro ajratib olish uchun o'lchovli algoritm
  2. ^ Stefan Szeider, Boshlang'ich o'zgaruvchan farq bilan minimal qondirilmaydigan formulalar sobit parametrlarga yo'naltiriladi
  3. ^ Minimal qondirilmaydigan kichik to'plamlarni hisoblash algoritmlari