$P \ne NP$, propositional proof complexity, and resolution lower bounds for the weak pigeonhole principle

Details $P \ne NP$, propositional proof complexity, and resolution lower bounds for the weak pigeonhole principle $P \ne NP$, propositional proof complexity, and resolution lower bounds for the weak pigeonhole principle

2003-04-28

arxiv.org/abs/cs/0304041v1

Proceedings of the ICM, Beijing 2002, vol. 3, 685--696

Computer Science

Computational Complexity

Scientific paper

Recent results established exponential lower bounds for the length of any Resolution proof for the weak pigeonhole principle. More formally, it was proved that any Resolution proof for the weak pigeonhole principle, with $n$ holes and any number of pigeons, is of length $\Omega(2^{n^{\epsilon}})$, (for a constant $\epsilon = 1/3$). One corollary is that certain propositional formulations of the statement $P \ne NP$ do not have short Resolution proofs. After a short introduction to the problem of $P \ne NP$ and to the research area of propositional proof complexity, I will discuss the above mentioned lower bounds for the weak pigeonhole principle and the connections to the hardness of proving $P \ne NP$.

Affiliated with

Also associated with

No associations

Rating

$P \ne NP$, propositional proof complexity, and resolution lower bounds for the weak pigeonhole principle does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with $P \ne NP$, propositional proof complexity, and resolution lower bounds for the weak pigeonhole principle, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and $P \ne NP$, propositional proof complexity, and resolution lower bounds for the weak pigeonhole principle will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-333838