We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [hard-instances]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
10
votes
3answers
498 views

Is embedding a solution feasible for SAT?

I am interested in "hard" individual instances of NP-complete problems. Ryan Williams discussed the SAT0 problem at Richard Lipton's blog. SAT0 asks whether a SAT instance has the specific solution ...
11
votes
2answers
695 views

What's the correlation between treewidth and instance hardness for random 3-SAT?

This recent paper from FOCS2013, Strong Backdoors to Bounded Treewidth SAT by Gaspers and Szeider talks about the link between the treewidth of the SAT clause graph and instance hardness. For ...
12
votes
3answers
331 views

Does there exist a hardest DCFL?

Greibach famously defined a language $H$, the so-called nondeterministic version of $D_2$, such that any CFL is an inverse morphic image of $H$. Does there exist a similar statement with DCFL, ...
3
votes
1answer
545 views

Easier and Harder instances of NP-complete problems?

Following previous questions here and here around $NP$-complete problems (and P vs NP). Are there "easier" or "harder" (sets of) instances of an $NP$-complete problem? If yes (which i assume), how a ...