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

SearchCloudSecurity

• Unify on-premises and cloud access control with SDP

One security framework available to organizations struggling with on-premises and cloud access control issues is a ...

• 6 AIOps security use cases to safeguard the cloud

Explore six AIOps security use cases in cloud environments, such as threat intelligence analysis and malware detection, as well ...

SearchNetworking

• Aruba product integrations advance its SASE strategy

Aruba's latest SASE-related integrations involve the Silver Peak-based SD-WAN, Threat Defense and the ClearPass Policy Manager. ...

• Wi-Fi 6 rollout requires careful review of network devices

Wi-Fi 6 is just one part of the overall enterprise network. Organizations need to evaluate several network components to ensure a...

SearchCIO

• Replacing vs. maintaining legacy systems

As CIOs embrace more digital technologies, it's important that they determine the current status of their legacy systems and ...

• Managing cybersecurity during the pandemic and in the new digital age

Roota Almeida, CISO at Delta Dental of New Jersey and Delta Dental of Connecticut, talks about the cybersecurity threats she's ...

• Enterprise architecture has business's ear at Scottish Water

Scottish Water's enterprise architecture team leader discusses how engaging with business leaders and software tools can help ...

SearchEnterpriseDesktop

• Incorporating zero trust into endpoint security

Zero trust is a complex term, but organizations that take security seriously must know what it is and how it can support existing...

• Keeping tabs on employees in the hybrid workplace

Companies want better ways to determine if their employees are mentally healthy or are at risk of a breakdown in the hybrid ...

• Top 6 endpoint security software options in 2021

The market for endpoint security software can be confusing to navigate for decision-makers, but this market roundup should help ...

SearchCloudComputing

• Ready to be a GCP architect? Try this quiz and see

This 10-question quiz, drawn from a new GCP certified professional cloud architect prep guide, helps identify your strengths and ...

• Choose the right serverless container service

Many IT pros consider serverless containers to be largely hype, while others say it offers real advances in serverless computing....

• IBM boosts vertical cloud push with financial services cloud

IBM doubles down on its investment in vertical markets, rolling out a financial services cloud that shares workloads with clouds ...

ComputerWeekly.com

• SAP users identify data skills shortage as importance of analytics spikes

Research from the SAP UK & Ireland User Group has demonstrated a data skills dearth among users and a delay in using the SAP Hana...

• The Secret IR Insider’s Diary – from Sunburst to DarkSide

From dealing with SolarWinds fallout to ransomware attacks, it’s been a busy few weeks for the Secret IR Insider, but they've ...

• London tech manifesto calls on next mayor to support tech industry

The London tech manifesto, put together by several tech organisations, calls on the city’s next mayor to support tech companies, ...

Close