Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Ben Bacarisse <ben@bsb.me.uk>
Newsgroups: sci.math
Subject: Re: Proof of P and NP
Date: Sat, 24 May 2025 01:15:22 +0100
Organization: A noiseless patient Spider
Lines: 40
Message-ID: <87sekux3s5.fsf@bsb.me.uk>
References: <KK7YP.90246$0DKa.14076@fx14.iad>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Sat, 24 May 2025 02:15:22 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="e251f1335b67f58efa9af8dd627a69d5";
	logging-data="361762"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/PcCcMiLlwZbjVFcOwaDepzF9G9nJXouc="
User-Agent: Gnus/5.13 (Gnus v5.13)
Cancel-Lock: sha1:a3iTczzN1KfYOerelMk9+RsO/f0=
	sha1:ClxluGRinP0krG4E42oyX5E5VGY=
X-BSB-Auth: 1.f9853ff8d3275f2142b1.20250524011522BST.87sekux3s5.fsf@bsb.me.uk
Bytes: 1931

Suresh Devanathan <idatarm@NOJUNKgmx.com> writes:

> Suppose you are trying to solve a Boolean satisfiability problem C[x]. Now
> convert the problem into probabilistic domain.
>
> For probability vector x
> C[x] = p
>      = p + 0*K*(B - p)
>      = lim K->infinity p + 1/K*K(B- p)
>      = B
>
>
> For friend
>   in case a satisfiability, B = 1
>   in case untestable, assume x_n=  0.5, B = 0
>
> For enemy,
>  in case a satisfiability, B = 0
>   in case untestable, assume x_n = 0.5, B = 1
>
>
> since by cook's thesis, even in 1 problem in NP proven to be P , every
> problem proven P.

Not right.  If a problem proven to be NP-complete is shown to be in P,
then P = NP.

> If
> reverse result is always true of enemy, the number of permutation is at
> least as great as 2^N
> where N is number of inputs, showing problem is be NP.

The problem must be NP-complete, not just in NP.

> complete proof

Not yet.

-- 
Ben.