Search for tag: "np"

ECS 220 8b:8.3-1 NL-completeness and logspace reductions

From  David Doty 0 likes 18 plays 0  

ECS 220 8a:8.2 NL and NPSPACE nondeterministic space-bounded computation and prover-verifier characterization

From  David Doty 0 likes 23 plays 0  

ECS 220 8a:8.1-3 relationship of time and space-bounded complexity classes

From  David Doty 0 likes 16 plays 0  

ECS 220 6b:7.2-3 computable enumerability

From  David Doty 0 likes 22 plays 0  

ECS 220 5c:6.6 why is it hard to prove P neq NP

From  David Doty 0 likes 16 plays 0  

ECS 220 5b:6.6-2 almost proof of Ladner's theorem

From  David Doty 0 likes 17 plays 0  

ECS 220 5b:6.6-3 clocked programs

From  David Doty 0 likes 13 plays 0  

ECS 220 5b:6.6-1 Ladner's theorem, existence of NP-intermediate problems

From  David Doty 0 likes 24 plays 0  

ECS 220 5a:6.4-4 an oracle making P=NP

From  David Doty 0 likes 24 plays 0  

ECS 220 5a:6.4-3 relativizing proofs

From  David Doty 0 likes 22 plays 0  

ECS 220 5a:6.4-2 P^SAT and P^NP

From  David Doty 0 likes 36 plays 0  

ECS 220 5a:6.4-1 oracles and relativized worlds

From  David Doty 0 likes 32 plays 0  

ECS 220 4c:6.3-4 P vs. NP vs. EXP nondeterministic time hierarchy theorem

From  David Doty 0 likes 17 plays 0  

ECS 220 4b:6.1-2 relation of NP to finding mathematical proofs

From  David Doty 0 likes 21 plays 0  

ECS 220 4a:6.1-3 collapse propagates up padding technique

From  David Doty 0 likes 27 plays 0  

ECS 220 4a:6.1-2 observations about the polynomial hierarchy and the great collapse

From  David Doty 0 likes 33 plays 0