isNPHard

P142025

predicate

Indicates that solving the associated problem is at least as hard as the hardest problems in NP, so no known polynomial-time algorithm can solve all its instances unless P = NP.

Try in SPARQL

All labels observed (1)

Label	Occurrences
isNPHard canonical	2

Description generation (PDg)

The one-sentence description above was generated by prompting gpt-5.1 with the predicate name and this instruction.

Instruction

Given a predicate that represents a relationship or action between entities, generate a one-sentence description explaining its meaning.  
# Instructions
Focus on describing the relationship, not the entities themselves. 
# Response Format
Begin the description with \' Indicates...\'

Input

Predicate: isNPHard

Generated description

Indicates that solving the associated problem is at least as hard as the hardest problems in NP, so no known polynomial-time algorithm can solve all its instances unless P = NP.

Sample triples (2)

Subject	Object
SAT problem	true ⓘ
Max-SAT	true ⓘ