info
Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
ℙ≠ℕℙ (solved)
7 views
Skip to first unread message
wij
Nov 21, 2022, 1:11:06 PM11/21/22
to
I am happy to announce the ℙ≠ℕℙ problem can be succinctly solved.
Define: bool Sat(Prog): Sat(f)==true iff ∃f(x), f(x) returns in P-time.
Sat is a language interpreter. Prog is a pass-by-value argument (e.g. TM description).
1. Problem(Sat)∈ℕℙ (from definition)
2. Problem(Sat)∉ℙ (from the HP proof, Sat will encounter an undecidable case)
Conclusion: ℙ≠ℕℙ
Define: bool Sat(Prog): Sat(f)==true iff ∃f(x), f(x) returns in P-time.
Sat is a language interpreter. Prog is a pass-by-value argument (e.g. TM description).
1. Problem(Sat)∈ℕℙ (from definition)
2. Problem(Sat)∉ℙ (from the HP proof, Sat will encounter an undecidable case)
Conclusion: ℙ≠ℕℙ
Ben Bacarisse
Nov 21, 2022, 2:34:26 PM11/21/22
to
wij <wyni...@gmail.com> writes:
> I am happy to announce the ℙ≠ℕℙ problem can be succinctly solved.
>
> Define: bool Sat(Prog): Sat(f)==true iff ∃f(x), f(x) returns in
> P-time.
This line has at least one abuse of notation and probably other, but I
> I am happy to announce the ℙ≠ℕℙ problem can be succinctly solved.
>
> Define: bool Sat(Prog): Sat(f)==true iff ∃f(x), f(x) returns in
> P-time.
can't parse it. It looks more like a math poem than an actual
well-formed formula.
> Sat is a language interpreter. Prog is a pass-by-value argument
> (e.g. TM description).
>
> 1. Problem(Sat)∈ℕℙ (from definition)
> 2. Problem(Sat)∉ℙ (from the HP proof, Sat will encounter an
> undecidable case)
(b) If Problem(Sat) (whatever that means) is not in P because of the
undeciability of halting, then it's not in NP either.
> Conclusion: ℙ≠ℕℙ
No.
--
Ben.
0 new messages