Loading...
Please wait, while we are loading the content...
Similar Documents
A new class of hard 3-sat instances (2005).
| Content Provider | CiteSeerX |
|---|---|
| Author | Znidaric, Marko |
| Abstract | We identify a new class of hard 3-SAT instances, namely a random 3-SAT problems having exactly one solution and as few clauses as possible. It is numerically shown that the running time of complete methods as well as of local search algorithms for such problems is larger than for random instances around the phase transition point. We therefore provide instances with an exponential complexity in the so-called “easy ” region, below the critical value of m/n. This puts a new light on the connection between the phase transition phenomenon and NP-completeness. |
| File Format | |
| Publisher Date | 2005-01-01 |
| Access Restriction | Open |
| Subject Keyword | Hard 3-sat Instance New Class New Light Exponential Complexity Random Instance Phase Transition Point Random 3-sat Problem Critical Value Running Time Local Search Algorithm Provide Instance So-called Easy Region Phase Transition Phenomenon Complete Method |
| Content Type | Text |
