Pytania otagowane jako hard-instances


2
Jaka jest korelacja między wysokością a twardością instancji dla losowego 3-SAT?
Ten ostatni artykuł z FOCS2013, Strong Backdoors to Bounded Treewidth SAT autorstwa Gaspersa i Szeidera mówi o związku między szerokością wykresu klauzuli SAT a twardością instancji. W przypadku losowych instancji 3-SAT, tj. Instancji losowo wybranych 3-SAT, jaka jest korelacja między szerokością wykresu klauzulowego a twardością instancji? „Twardość wystąpienia” może być …


3
Czy osadzenie rozwiązania jest możliwe dla SAT?
Interesują mnie „twarde” pojedyncze przypadki problemów z NP. Ryan Williams omówił problem SAT0 na blogu Richarda Liptona . SAT0 pyta, czy instancja SAT ma konkretne rozwiązanie składające się ze wszystkich zer. To skłoniło mnie do myślenia o konstruowaniu instancji SAT, które prawdopodobnie będą „trudne”. Rozważmy wystąpienie SAT z klauzulami i …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.