# 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