Pytania oznaczone «sat»

14
Jaka jest złożoność Median-SAT?

Niech będzie formułą CNF z n zmiennymi i klauzulami m . Niech t ∈ { 0 , 1 } n reprezentuje przypisanie zmiennej, a f φ ( t ) ∈ { 0 , … , m } zliczają liczbę klauzul spełnionych przez przypisanie zmiennej do φ . Następnie zdefiniuj Median-SAT jako problem obliczania mediany wartości f φ ( t ) dla...

14
odmiany SAT

Spojrzałem w Internecie, ale nie mogłem znaleźć żadnej „dużej listy” wariantów problemu SAT. Oprócz (wspólnego) SAT, k-SAT, MAX-kSAT, Half-SAT, XOR-SAT, NAE-SAT jakie jeszcze są warianty? (również będzie to bardzo przydatne, jeśli podano klasy złożoności (tam, gdzie to...

12
Mierzenie losowości wzorów CNF

Powszechnie wiadomo, że formuły CNF można z grubsza podzielić na 2 szerokie klasy: losowe i strukturalne. Strukturalne formuły CNF, w przeciwieństwie do losowych formuł CNF, wykazują pewien porządek, pokazując wzorce, które prawdopodobnie nie wystąpią przypadkowo. Można jednak znaleźć formuły...