Definition

# P versus NP (polynomial versus nondeterministic polynomial)

P versus NP (polynomial versus nondeterministic polynomial) refers to a theoretical question presented in 1971 by Leonid Levin and Stephen Cook, concerning mathematical problems that are easy to solve (P type) as opposed to problems that are difficult to solve (NP type).

Any P type problem can be solved in "polynomial time." (A polynomial is a mathematical expression consisting of a sum of terms, each term including a variable or variables raised to a power and multiplied by a coefficient.) A P type problem is a polynomial in the number of bits that it takes to describe the instance of the problem at hand. An example of a P type problem is finding the way from point A to point B on a map. An NP type problem requires vastly more time to solve than it takes to describe the problem. An example of an NP type problem is breaking a 128-bit digital cipher. The P versus NP question is important in communications, because it may ultimately determine the effectiveness (or ineffectiveness) of digital encryption methods.

An NP problem defies any brute-force approach at solution, because finding the correct solution would take trillions of years or longer even if all the supercomputers in the world were put to the task. Some mathematicians believe that this obstacle can be surmounted by building a computer capable of trying every possible solution to a problem simultaneously. This hypothesis is called P equals NP. Others believe that such a computer cannot be developed (P is not equal to NP). If it turns out that P equals NP, then it will become possible to crack the key to any digital cipher regardless of its complexity, thus rendering all digital encryption methods worthless.

This was last updated in September 2005

## Content

Find more PRO+ content and other member only offers, here.

#### Start the conversation

Send me notifications when other members comment.

## SearchCloudSecurity

• ### How to effectively manage the cloud logs of security events

Cloud logs of security events produce an abundance of data. Expert Dave Shackleford discusses how to filter through it and get to...

• ### How the Flip Feng Shui technique undermines cloud security

The Flip Feng Shui attack against hypervisors could have both short and long-term effects on enterprises. Expert Ed Moyle ...

• ### How cloud endpoint protection products benefit enterprises

Cloud endpoint protection products are outpacing standard endpoint protections. Expert Frank Siemons discusses the evolution of ...

## SearchNetworking

• ### Cumulus NOS, Edgecore switch bundle unlikely to beat incumbent vendors

Analysts are skeptical of networking supplier Cumulus's entry into the hardware business. The vendor is selling and supporting an...

• ### Trigger gets props among hot next-gen network automation tools

This week, bloggers look into network automation tools, incident response, and the new reality of MPLS and SD-WAN.

• ### Enterprises finding high value in 25 GbE, 100 GbE switches

Research finds shipments of 25 GbE and 100 GbE switches are outpacing 10/40 GbE hardware, as companies find more value in the ...

## SearchCIO

• ### Oculus trial: Even if Facebook loses, VR to prevail

The outcome of the Oculus trial is up in the air, but VR is gaining ground. Also in Searchlight: Oracle faces discrimination suit...

• ### Securing a board appointment: CIO requirements and benefits

A corporate board appointment can give a CIO invaluable perspective on running a business, but to get one, deep expertise and a ...

• ### PrivacyCon: Tech's assault on (obliteration of?) consumer privacy

The attack on consumer privacy by new tech is huge and growing, enabled by consumers and greased by profit; in other words, a ...

## SearchConsumerization

• ### Android, Windows tablets from HP take aim at business users

HP released a new line of tablets targeting business users. The HP Pro Slate 8 and Pro Slate 12 run Android and cost \$449 and ...

• ### Microsoft to lay off 18,000, Nokia X moves to Windows Phone

Microsoft will lay off 18,000 people over the next year while the Nokia X line of Android smartphones, which was unveiled earlier...

• ### Microsoft Surface Pro 3 vs. Microsoft Surface Pro 2

Surface Pro 2 and Surface Pro 3 are different enough that Microsoft is keeping both on the market as competing products. Which ...

## SearchEnterpriseDesktop

• ### Prepare for the challenging move to Windows 10

Organizations can cling to past versions of Windows as long as they want. But, eventually, they will have to accept Windows 10, ...

Before making a move to Windows 10, IT admins need to know how licensing, hardware and management are different. They also must ...

• ### Give Windows 10 disk space a clean sweep

There are multiple ways to keep Windows 10 running smoothly, such as clearing the clutter of old files and applications. A more ...

## SearchCloudComputing

• ### Words to go: Google cloud storage services

When it comes to cloud storage, going in blind will cause inefficiency and high costs. Familiar yourself with these key Google ...

• ### Cloud, IoT to drive enterprise IT trends in 2017

Cloud computing has evolved quite a bit in the last few years, but it still has far to go. Technologies such as big data, ...

• ### Build cloud web services with microservices

Building cloud web services with microservices provides benefits, such as scalability, and allows enterprise apps to access new ...

## ComputerWeekly

• ### IoT Trends & Challenges in ASEAN

In this e-guide, we put a South-East Asian spin on the global phenomenon that is the Internet of Things (IoT). With billions of ...

• ### BT draws fire over broadband price hike

Consumer broadband groups have hit out after BT put up its broadband prices

• ### Pay rises tipped for IT security and data analysis roles in 2017

Increase in high-profile data breaches and the need for data insight are seen as contributory factors in salary rises for IT ...

Close