# The status of the P versus NP problem

@article{Fortnow2009TheSO, title={The status of the P versus NP problem}, author={Lance Fortnow}, journal={Commun. ACM}, year={2009}, volume={52}, pages={78-86} }

It's one of the fundamental mathematical problems of our time, and its importance grows with the rise of powerful computers.

#### Topics from this paper

#### 251 Citations

The GCT program toward the P vs. NP problem

- Mathematics, Computer Science
- CACM
- 2012

Exploring the power and potential of geometric complexity theory with a focus on LaSalle's inequality. Expand

Mathematics in the age of the Turing machine

- Computer Science, Mathematics
- Turing's Legacy
- 2014

The article gives a survey of mathematical proofs that rely on computer calculations and formal proofs, as well as some examples from the literature. Expand

A Polynomial Time Algorithm for a NPC Problem

- Computer Science
- ArXiv
- 2021

It is introduced a so called ‘Multi-stage graph Simple Path’ (MSP for short) problem and proved that SAT problem can be polynomially reducible to the MSP problem in this very small paper. To solve… Expand

Inductive Complexity of P versus NP Problem - Extended Abstract

- Mathematics, Computer Science
- UCNC
- 2012

An upper bound on the inductive complexity of second order of the P versus NP problem is determined using the complexity measure developed in [7,3,4] and the extensions obtained by using inductive register machines of various orders in [1,2]. Expand

A Simple Proof of P versus NP

- 2018

P versus NP is one of the most important and unsolved problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? Another major complexity class is… Expand

Graph matching in theory and practice

- Computer Science
- Commun. ACM
- 2016

A theoretical breakthrough in graph isomorphism excites complexity experts, but will it lead to any practical improvements?

Multinational War is Hard

- Mathematics, Computer Science
- ArXiv
- 2015

In this paper, we show that the problem of determining whether one player can force a win in a multiplayer version of the children's card game War is PSPACE-hard. The same reduction shows that a… Expand

An Interesting Perspective to the P versus NP Problem

- Mathematics
- 2015

We discuss the P versus NP problem from the perspective of addition operation about polynomial functions. Two contradictory propositions for the addition operation are presented. With the proposition… Expand

On the P VS NP Question: A New Proof of Inequality

- Computer Science
- 2021

It is proved that the cost of the minimal implementation of core function increases with n exponentially, which is equivalent to proving that P and NP do not coincide. Expand

A polynomial-time algorithm for the maximum clique problem

- Computer Science
- 2013 IEEE/ACIS 12th International Conference on Computer and Information Science (ICIS)
- 2013

A polynomial-time algorithm is presented, which detects the maximum clique of a given graph through a recursive approach, which causes every problem in NP to have a polynometric solution, which leads to the equality of P and NP complexity classes. Expand

#### References

SHOWING 1-10 OF 63 REFERENCES

The status of the P versus NP problem

- Computer Science
- 2009

It's one of the fundamental mathematical problems of our time, and its importance grows with the rise of powerful computers.

PRIMES is in P

- Mathematics
- 2004

We present an unconditional deterministic polynomial-time algorithm that determines whether an input number is prime or composite.

Parity, circuits, and the polynomial-time hierarchy

- Mathematics, Computer Science
- 22nd Annual Symposium on Foundations of Computer Science (sfcs 1981)
- 1981

A super-polynomial lower bound is given for the size of circuits of fixed depth computing the parity function and connections are given to the theory of programmable logic arrays and to the relativization of the polynomial-time hierarchy. Expand

Parameterized Complexity

- Computer Science
- Monographs in Computer Science
- 1999

An approach to complexity theory which offers a means of analysing algorithms in terms of their tractability, and introduces readers to new classes of algorithms which may be analysed more precisely than was the case until now. Expand

A Fast Monte-Carlo Test for Primality

- Mathematics, Computer Science
- SIAM J. Comput.
- 1977

A uniform distribution a from a uniform distribution on the set 1, 2, 3, 4, 5 is a random number and if a and n are relatively prime, compute the residue varepsilon. Expand

The Intractability of Resolution

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1985

Abstract We prove that, for infinitely many disjunctive normal form propositional calculus tautologies ξ, the length of the shortest resolution proof of ξ cannot be bounded by any polynomial of the… Expand

The complexity of theorem-proving procedures

- Computer Science, Mathematics
- STOC
- 1971

It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be “reduced” to the problem of determining whether a given propositional formula is a… Expand

Probabilistically checkable proofs

- Computer Science
- CACM
- 2009

Can a proof be checked without reading it?

Reducibility among combinatorial problems" in complexity of computer computations

- Computer Science
- 1972

In his 1972 paper, Reducibility Among Combinatorial Problems, Richard Karp used Stephen Cooks 1971 theorem that the boolean satisfiability problem is. Expand

Computational Complexity

- Computer Science
- Encyclopedia of Cryptography and Security
- 2011

Computational complexity theory provides a foundation for most of modern cryptography, where the aim is to design cryptosystems that are “easy to use” but “hard to break”. Expand