✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-233

P, NP, NP-Hard, and NP-Complete Problems

P, NP, NP-hard, and NP-complete are important complexity classes used to classify computational problems according to how efficiently they can be solved or how efficiently proposed solutions can be verified. These classifications help explain the difficulty of many fundamental problems in computer science.

Explanation

Overview

Complexity classes group computational problems according to their computational properties. P contains decision problems solvable in polynomial time by a deterministic algorithm. NP contains decision problems whose proposed solutions can be verified in polynomial time. NP-hard problems are at least as hard as every problem in NP under an appropriate polynomial-time reduction. NP-complete problems are both in NP and NP-hard.

Key concepts

name: Core idea; description: The central focus of p, np, np-hard, and np-complete problems is the capability described here: P, NP, NP-hard, and NP-complete are important complexity classes used to classify computational problems according to how efficiently they can be solved or how efficiently proposed solutions can be verified. These classifications help explain the difficulty of many fundamental problems in computer science.; name: Problem context; description: P, NP, NP-Hard, and NP-Complete Problems is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using p, np, np-hard, and np-complete problems, check its assumptions, input requirements, expected output, and resource constraints.

Example

scenario: Boolean Satisfiability Problem (SAT).; input: A Boolean formula containing variables, logical operators, and clauses.; question: Does there exist an assignment of true and false values that makes the formula true?; verification: Given a proposed assignment, evaluate the formula to check whether it is satisfied.; classification: SAT is NP-complete.; explanation: A proposed satisfying assignment can be checked in polynomial time, so SAT belongs to NP. SAT is also NP-hard because every problem in NP can be reduced to it in polynomial time.

Applications

Cryptography and computational security research.; Scheduling and resource allocation.; Circuit and hardware verification.; Artificial intelligence and constraint solving.; Optimization and operations research.

Limitations

The suitability of p, np, np-hard, and np-complete problems depends on the exact problem requirements and the assumptions made about the input.; An implementation of p, np, np-hard, and np-complete problems can fail if its boundary conditions, data representation, or required invariants are handled incorrectly.; For p, np, np-hard, and np-complete problems, evaluate representative and unusually difficult inputs; a single small demonstration is not enough to establish reliability.

Common misconceptions

NP does not mean that a problem cannot be solved in polynomial time.; NP-hard does not automatically mean NP-complete.; NP-complete problems are decision problems that are both in NP and NP-hard.; P versus NP remains an open mathematical problem.; A problem being NP-complete does not prove that no efficient algorithm exists.

Example or application

Scenario

Boolean Satisfiability Problem (SAT).

Input

A Boolean formula containing variables, logical operators, and clauses.

Question

Does there exist an assignment of true and false values that makes the formula true?

Verification

Given a proposed assignment, evaluate the formula to check whether it is satisfied.

Classification

SAT is NP-complete.

Explanation

A proposed satisfying assignment can be checked in polynomial time, so SAT belongs to NP. SAT is also NP-hard because every problem in NP can be reduced to it in polynomial time.

Definition

Complexity classes group computational problems according to their computational properties. P contains decision problems solvable in polynomial time by a deterministic algorithm. NP contains decision problems whose proposed solutions can be verified in polynomial time. NP-hard problems are at least as hard as every problem in NP under an appropriate polynomial-time reduction. NP-complete problems are both in NP and NP-hard.

Problem Classes

NameFull NameDescriptionExamplesImportant Note

P

Polynomial Time

The class of decision problems that can be solved in polynomial time by a deterministic algorithm.

  • Checking whether a graph is connected.

  • Determining whether a number is even.

  • Finding whether a path exists between two vertices in a graph.

Polynomial time commonly includes complexities such as O(n), O(n²), and O(n³). A polynomial-time algorithm is generally considered efficient in theoretical complexity analysis, although high-degree polynomials can still be impractical.

NP

Nondeterministic Polynomial Time

The class of decision problems for which a proposed yes-solution can be verified in polynomial time by a deterministic algorithm.

  • Determining whether a graph contains a Hamiltonian cycle.

  • Determining whether a Boolean formula has a satisfying assignment.

  • Determining whether a graph contains a clique of at least a specified size.

NP does not mean non-polynomial. It means nondeterministic polynomial time. It is unknown whether every problem in NP also belongs to P.

NP-Hard

Nondeterministic Polynomial-Time Hard

A problem is NP-hard if every problem in NP can be transformed into it through a polynomial-time reduction, using the selected reduction model.

  • The optimization version of the Traveling Salesperson Problem.

  • Certain scheduling optimization problems.

  • General optimization versions of difficult combinatorial problems.

An NP-hard problem does not necessarily belong to NP. It may be an optimization problem or even a problem outside the class of decision problems.

NP-Complete

Nondeterministic Polynomial-Time Complete

A decision problem is NP-complete if it belongs to NP and is also NP-hard.

  • Boolean Satisfiability Problem (SAT).

  • 3-SAT.

  • Hamiltonian Cycle decision problem.

  • Clique decision problem.

  • Vertex Cover decision problem.

If any NP-complete problem has a deterministic polynomial-time algorithm, then every problem in NP can be solved in polynomial time, establishing P = NP.

Relationships

StatementExplanation

P is a subset of NP.

If a problem can be solved efficiently, a proposed solution can also be verified efficiently.

Every NP-complete problem is NP-hard.

NP-completeness requires both membership in NP and NP-hardness.

Not every NP-hard problem is NP-complete.

An NP-hard problem may not belong to NP.

Whether P equals NP is unknown.

No proof has established either P = NP or P ≠ NP.

Why These Classes Matter

  • They provide a common language for describing computational difficulty.

  • They help determine whether an exact algorithm is likely to scale.

  • They support proofs that certain problems are computationally difficult.

  • They guide the use of approximation algorithms, heuristics, and specialized solvers.

  • They connect apparently different problems through polynomial-time reductions.

Common Misconceptions

  • NP does not mean that a problem cannot be solved in polynomial time.

  • NP-hard does not automatically mean NP-complete.

  • NP-complete problems are decision problems that are both in NP and NP-hard.

  • P versus NP remains an open mathematical problem.

  • A problem being NP-complete does not prove that no efficient algorithm exists.

Applications

  • Cryptography and computational security research.

  • Scheduling and resource allocation.

  • Circuit and hardware verification.

  • Artificial intelligence and constraint solving.

  • Optimization and operations research.

Related Topics

  • INFO-CS-ADS-232

  • INFO-CS-ADS-234

  • INFO-CS-ADS-235

  • INFO-CS-ADS-236

  • INFO-CS-ADS-237

Practice Questions

QuestionAnswer

What is the main property of problems in P?

They can be solved in polynomial time by a deterministic algorithm.

What makes a problem belong to NP?

A proposed yes-solution can be verified in polynomial time.

What two properties define an NP-complete problem?

It must belong to NP and be NP-hard.

Has the P versus NP question been solved?

No. It remains an open problem.

Key Concepts

NameDescription

Core idea

The central focus of p, np, np-hard, and np-complete problems is the capability described here: P, NP, NP-hard, and NP-complete are important complexity classes used to classify computational problems according to how efficiently they can be solved or how efficiently proposed solutions can be verified. These classifications help explain the difficulty of many fundamental problems in computer science.

Problem context

P, NP, NP-Hard, and NP-Complete Problems is relevant when a computational task requires the behavior or capability described by this topic.

Correct use

Before using p, np, np-hard, and np-complete problems, check its assumptions, input requirements, expected output, and resource constraints.

Limitations

  • The suitability of p, np, np-hard, and np-complete problems depends on the exact problem requirements and the assumptions made about the input.

  • An implementation of p, np, np-hard, and np-complete problems can fail if its boundary conditions, data representation, or required invariants are handled incorrectly.

  • For p, np, np-hard, and np-complete problems, evaluate representative and unusually difficult inputs; a single small demonstration is not enough to establish reliability.

Learning Objectives

  • Explain the central idea and purpose of p, np, np-hard, and np-complete problems.

  • Identify the assumptions, inputs, and conditions relevant to p, np, np-hard, and np-complete problems.

  • Evaluate an application of p, np, np-hard, and np-complete problems for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Advanced Algorithm Theory and Applications

Suggest a correction or source · More in Algorithms & Data Structures