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

• ### Cloudflare Access takes on VPNs with reverse proxy approach

Cloudflare takes inspiration from Google's BeyondCorp with a new service called Cloudflare Access, which aims to replace ...

• ### TLS 1.3: What it means for enterprise cloud use

The latest draft version of TLS 1.3 is out, and it will likely affect enterprises that use cloud services. Expert Ed Moyle ...

• ### The biggest cloud security threats, according to the CSA

The Cloud Security Alliance reported what it found to be the biggest cloud security threats. Expert Rob Shapland looks at how ...

## SearchNetworking

• ### ThousandEyes-Juniper pact focuses on hybrid WANs

ThousandEyes and Juniper boost visibility for hybrid WANs; IDC records sharp rise in cloud spending; and a vendor group issues ...

• ### ExtremeLocation latest addition to Extreme wireless portfolio

Extreme Networks is targeting retailers with a new set of services, called ExtremeLocation. The latest technology adds ...

• ### Take network configuration management tools to the next level

Script management systems and intent-based networking are driving the future of network configuration management tools, shifting ...

## SearchCIO

• ### Some may not know it, but companies want CIOs with cloud expertise

Organizations know what benefits cloud computing can bring -- and they're seeking out IT leaders with cloud expertise to make ...

• ### 'Patient journey' propels hospital's digital transformation

The chief innovation officer at Boston Children's Hospital explains how digital technologies are changing the 'patient journey' ...

• ### Wayfair's chief architect talks AI-driven innovation, impactful IT

Wayfair sells home furnishings, but under the covers, it's a tech juggernaut. Chief Architect Ben Clark explains how AI-driven ...

## SearchEnterpriseDesktop

• ### Ten Windows 10 Fall Creators Update features to know

Microsoft introduced some significant changes to Windows 10 in the Fall Creators Update. The My People app, for example, lets ...

• ### Guard the line with Windows Defender features

The Windows 10 Fall Creators Update took Windows 10 security up a notch by adding advanced features to Windows Defender, ...

• ### Ready to master virtualization-based security in Windows 10?

Put your knowledge of virtualization-based security in Windows 10 on the line with this quiz covering the ins and outs of ...

## SearchCloudComputing

• ### Gauge your knowledge of cloud providers' AI technologies

As enterprise interest grows, major cloud providers continue to unveil machine learning and AI services. See how much you know ...

• ### Google Cloud Dedicated Interconnect offers VPN alternative

Google's Dedicated Interconnect enables an enterprise to privately connect its data center to the public cloud. Here's a ...

• ### Meltdown-Spectre bugs hit cloud usage less than first feared

IT shops expected their cloud usage to flag due to recent chip bugs, but most environments survived the patches unscathed.

## ComputerWeekly.com

• ### Do website design platforms pose too big a security risk?

Cloud-based website design platforms are booming in popularity because of their simplicity and affordability, but business ...

• ### Mastercard sets biometric ID deadline for banks

Mastercard has committed to guaranteeing that every one of its customers will have access to biometric authentication services by...

• ### Modern methodology gives Sweden’s 100-year-old SKF a digital push

Long-established engineering company takes a leaf out of the startup guide to software development

Close