Name
Abstract | ||
|---|---|---|
Extending the theory of complexity cores, it is proved, assuming NP co-NP, that there exist collections of tautologies of exponential density which have only non-polynomially long proofs under every sound proof system. |
Year | DOI | Venue |
|---|---|---|
1987 | 10.1007/3-540-50241-6_43 | CSL |
Keywords | Field | DocType |
hard-to-prove formulas,complexity cores | Discrete mathematics,Combinatorics,Tautology (logic),Exponential function,Computer science,Turing machine,Mathematical proof,Time complexity | Conference |
ISBN | Citations | PageRank |
3-540-50241-6 | 2 | 0.39 |
References | Authors | |
14 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Uwe Schöning | 1 | 998 | 105.69 |