NPC
Table of Contents
TIME(t(n)): the collection of languages that are decidable by an O(t(n)) time TM. ==> P
NTIME(t(n)): the collection of languages that are decidable by an O(t(n)) time NTM. ==> NP
Assume t(n)>n. Every t(n) time single tape NTM equals to a `\(2^{O(t(n))}\)` time single tape Deterministic TM
Assume t(n)>n. Every t(n) time multi-tape TM equals to a `\(O(t^2(n))\)` time single tape TM.
a language is in NP <=> decided by some polynomial time NTM
1 Prove clique is in NP
1.1 Proof 1:
``` V=on input <<G,k>,c>:
- Test whether c is a subgraph of k nodes in G
- Test whether G contains all edgesconnecting nodes in c
- if both pass accept, otherwise reject.
```
1.2 Proof 2:
``` N=on input <G,k>:
- non-deterministically select a subset c of k nodes in G
- Test whether c contains all edges connecting nodes in c
- if yes, accept. Otherwise reject.
```
language B is in NPC if:
- B is NP
- every A in NP is polynomial time reducible to B