P Is Not Equal to NP

Loading...
Thumbnail Image

Embargo Date

Related Collections

Degree type

Discipline

Subject

Funder

Grant number

License

Copyright date

Distributor

Related resources

Contributor

Abstract

This paper presents a proof of the conjecture that the complexity classes P and NP are not equal. The proof involves showing that a particular problem in NP cannot be solved in polynomial time. The problem in question is the satisfiability problem for logical expressions in conjunctive normal form (CSAT). The strategy of the proof is to construct what amounts to the most efficient algorithm for CSAT and then show that this algorithm does not run in polynomial time. The algorithm is constructed by constructing, from first principles, a set of constraints that any efficient algorithm for CSAT must satisfy. The constraints are made so restrictive that any two algorithms that satisfy all of them are essentially interchangeable.

Advisor

Date Range for Data Collection (Start Date)

Date Range for Data Collection (End Date)

Digital Object Identifier

Series name and number

Publication date

1989-10-01

Volume number

Issue number

Publisher

Publisher DOI

Journal Issues

Comments

University of Pennsylvania Department of Computer and Information Science Technical Report No. MS-CIS-89-72.

Recommended citation

Collection