Generalized first-order spectra and polynomial-time recognizable sets.

Fagin, R. (1974). Generalized first-order spectra and polynomial-time recognizable sets. Complexity of Computation, 38(1), 43-73.

Type

Journal article

Intellectual base

Primary research

Year

1974

Link

no authoritative link yet

Cited from

systems_cybernetics

Cited by

1 citation across 1 artifact.

Primes

• Complexity
  • Practical consequences pervade computing: cryptography relies on NP-hard assumptions (integer factoring, discrete logarithm) for security; SAT-solver advances have enabled industrial applications (hardware verification, model checking, planning) once thought intractable; parameterized-complexity analysis identifies problem features that make real instances tractable despite worst-case hardness

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:85f3683ec747 · see in the full table