Front Page

AllPages RecentChanges Links to this page Edit this page Search Entry portal Advice For New Users

This is very much the early stage of a work in progress. I'm extending, enhancing, clarifying and culling as time permits and as I get feedback. If you have comments then feel free to send email to me at PvsNP (at) solipsys.co.uk

This is a small wiki that I wrote to help me write a series of articles/pages/items about the "P vs NP" problem. If you're interested you can send me email and ask for a registration key.

Here we are so far - you really want to go to the Introduction next.

Table of Contents:

• Introduction
• What is a problem?
• Time complexity
• What is P?
• What is NP?
• P Problems are in NP.
• What does it mean to say problem A is harder than problem B?
• Example NP problems,
• and why are they hard?
• What is NP-Complete (NPC)?
• How do you prove a problem is NPC?
• Graph Three-Coloring is NPC.

• What's a Turing machine
• Emulating a Turing Machine in logic
• Emulating logic in 3-coloring
• Some history