In: Computer Science
Explain the logical structure of the following set of propositions - a theory.
1.The set of languages accepted (decided) by deterministic Turing machines = the set of languages accepted (decided) by nondeterministic Turing machines
2. PATH belongs to P
3. TAUTOLOGY is a member of coNP
4. 2 definitions for NP (1 in terms of a polynomial verifier 2 in terms of a nTM) are equivalent
5. PSPACE = NPSPACE
6. NP is a subset of PSPACE
7. SAT belongs to NP
8. TQBF belongs to PSPACE
9. P is a subset of PSPACE
10. NP is a subset of PSPACE %3D CONP = P %3D
11. P is a subset of NP
12. If P = NP then NP
13. If SAT belongs to P, then a certificate of an arbitrary YES instance of SAT can be found efficiently
14. Matching problem belongs to P
15. P is subset of the intersection of NP and coNP
16. P = NP then the entire pqlynomial hierarchy collapses to P
17. NP is a subset of sharp P
18. Proof checking belongs to P
19. Short proof belongs to NP
20. Elegant theory belongs to NP
21. SUBGRAPH ISOMORPHISM is NP-complete