World's most popular travel blog for travel bloggers.

P is closed under power of integer

, , No Comments
Problem Detail: 

I'm new in this area of complexity and I'm trying to get into it by understanding basic proofs.

I want to prove that if $L\in P$, so $L^k\in P$, where $k$ is non-negative integer.

How to prove it in the "official" way?

Asked By : Nick
Answered By : Yuval Filmus

Here is the proof for NP. You generalize it to P.

Let $L$ be a language in NP. Thus there is a polytime non-deterministic Turing machine $T$ that accepts $x$ iff $x \in L$. Using $T$, we can construct a non-deterministic Turing machine that accepts $L^k$. On input $x$, the machine first guesses (non-deterministically) a partition $x=x_1\ldots x_k$, and then verifies that $x_1,\ldots,x_k \in L$ using $T$. It's not hard to check that this machine also runs in polynomial time.

When generalizing the argument to P we have to implement the partition guessing in a deterministic way – details left to you.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback