Thinking·OS
← Back
In graph Frontier
Computer ScienceAlgorithmsEstablished

NP-complete

In computational complexity theory, NP-complete problems are the hardest of the problems to which solutions can be verified quickly.

NP-completeComputational complexity theoryOptimizationComputability theoryAnalysis of algorithmsAlgorithmNP-completenessClass PBQP (quantum complexity)

At a glance

Type
scale
Disciplines 2
Computer ScienceAlgorithms
Mental models 0
—
Role in the graph
Cross-disciplinary bridge
reaches 6 discipline lenses

Key signals

Cross-disciplinary reach
Disciplines
2
  • Computer Science
  • Algorithms
Evidence & development

Dependencies

What this concept builds on and what it makes possible — derived from the atlas’s dependency, causal and structural relations, not from every related edge.

System context

NP-completeis part ofComputational complexity theoryEstablished

Open Computational complexity theory →

NP-complete is part of computational complexity theory.

Mechanism: NP-complete problems are the hardest in NP: no known algorithm solves them quickly, and a fast solution to one would crack them all.

Sources:

Structural role & consequence

Interpreted from the current atlas graph — what the connections mean, not just how many there are.

  • 50% of its relationships cross field boundaries, reaching 6 other disciplines — unusual in a discipline where most concepts stay within their field.

    structural · Structural graph analysis — not a claim of importance, causation or history.

  • Currently dark in the atlas: no key date stored · 2 of 2 of its relations lack claim-level evidence.

    atlas representation · Describes the current Thinking OS representation, not the state of the world.

  • Structural neighbourhood: 2 → 28 → 108 concepts reachable within 3 hops.

    structural · Structural reach — being reachable is not the same as being understood.

50%

cross-field
1 within-field, 1 cross-field

0 of 2 relations carry evidence · concept has a verified source

Strengths & constraints

Strengths

  • Cross-disciplinary connector — 50% of its relationships cross field boundaries. structural

Constraints

  • Evidence coverage currently thin in the atlas — few of its relationships carry claim-level evidence. atlas representation
  • No dated history stored — the atlas records no key date for this concept. atlas representation

Conditions

  • Read structurally — most of its relationships carry no external evidence yet, so claims here are graph-derived. structural

Seen through each discipline

How this concept sits in each of its fields — derived from its real connections in the graph, not asserted.

Computer Science

Through this lens it connects to Computational complexity theory.

NP-complete through the Computer Science lens →

Algorithms

Through this lens it connects to Computational complexity theory.

NP-complete through the Algorithms lens →

Concepts that look related but are not yet connected here — candidates for a connection to reason about, not established links.

This idea also appears in…

The same structure shows up in other disciplines. These are real recurrences drawn from the graph — a starting point for asking “what carries over, and what changes?”

Concepts

  • OptimizationOptimizationEngineeringEconomics

    crosses a discipline boundary

The scientific picture
  • Connects 2 other ideas across 2 disciplines.
  • A cross-disciplinary bridge — its connections reach into 6 other fields.
  • Most of its connections are of the “Kind & structure” kind.

Derived from the graph’s real structure — observations, not a score.

Sources