Loading...
Please wait, while we are loading the content...
Similar Documents
Beyond NP: the QSAT phase transition (1998)
| Content Provider | CiteSeerX |
|---|---|
| Author | Gent, Ian P. Walsh, Tobby |
| Description | We show that phase transition behaviour similar to that observed in NP-complete problems like random 3-Sat occurs in Pspace-complete problems like random Qsat. Most of the differences in phase transition behaviour that Cadoli et al. report for random Qsat problems (for instance, no fixed point and no easy-hard-easy pattern) are largely due to the presence of trivially unsatisfiable problems. Once they are removed, we see behaviour more familiar to us from Sat and other NP-complete domains. There do, however, appear to be some slight differences. When problems contain short clauses, there is a large gap between worst case behaviour and median, and the easy-hard-easy pattern is restricted to the higher percentiles of the search cost. In addition, our theory of constrainedness appears to be rather less accurate at predicting the precise location of the phase transition compared to many NP-complete problems. We conjecture that the accuracy may be influenced by the super-exponential size of... |
| File Format | |
| Language | English |
| Publisher | AAAI Press |
| Publisher Date | 1998-01-01 |
| Access Restriction | Open |
| Subject Keyword | Pspace-complete Problem Short Clause Random Qsat Problem Many Np-complete Problem Super-exponential Size Slight Difference Np-complete Problem Phase Transition Behaviour Phase Transition Case Behaviour Qsat Phase Transition Random 3-sat Occurs Search Cost Unsatisfiable Problem Easy-hard-easy Pattern Large Gap Precise Location Np-complete Domain Fixed Point Random Qsat |
| Content Type | Text |
| Resource Type | Article |
