- Let U be a unary language (it consists of strings of the form ). Show that if U is NP-Complete, then P = NP.
- Construct a decidable language in P/poly that is NOT in P
- If P = NP, then there’s a language in EXP that requires exponential circuits. For this problem you’ll need the result

. Note the paradoxical nature of the result: an upper bound (P = NP) implies a lower bound. For the definition of , see this chapter.

### Like this:

Like Loading...

*Related*

## Leave a comment

Comments feed for this article