Post #2712421
2026-04-26 20:54 UTC
@esap@noc.social
ISTM that a program is in fact a spec for itself, so what does this tell us about P = NP?
Replies (1)
-
@esap@noc.social 2026-04-27 15:36
@RonJeffries@mastodon.social Depending on your notion of specification... P=NP depends on whether polynomial time complexity classes have an essential distinction between verification and implementation. Specification could be viewed as 3rd distinct phase of process, or unified with either tests (~in NP) or with implementation (~in P). If P=NP, all these can be easily unified. If P != NP, the tests/specifications have different complexity than the implementation, and they have different role due to complexity.