Path: ...!news.misty.com!3.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: wij <wyniijj5@gmail.com>
Newsgroups: comp.theory
Subject: Re: Improved =?UTF-8?Q?=E2=84=99=E2=89=A0=E2=84=95=E2=84=99?= proof
Date: Wed, 05 Jun 2024 15:33:17 +0800
Organization: A noiseless patient Spider
Lines: 99
Message-ID: <22b8a8909a18d0b9e6fbf9285b20f903b1e5ab48.camel@gmail.com>
References: <108d3c553ccae9c7e6eeb1b8b1a85a52b8b0b78d.camel@gmail.com>
	 <eed8bcaeee2337a7d842401b4bd6e2e409ddc213.camel@gmail.com>
	 <9bf939d70b9ee022a01a7b1dd9eaa705da397d88.camel@gmail.com>
	 <v3n7fk$1ot7$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Wed, 05 Jun 2024 09:33:19 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="77ba2c3100ec53a40d8543bab07882bc";
	logging-data="934560"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/BqbzK3OKkH0UW1XZD/DGe"
User-Agent: Evolution 3.50.2 (3.50.2-1.fc39)
Cancel-Lock: sha1:6UOwJv8HBQDispSKO3nUmQRkBKc=
In-Reply-To: <v3n7fk$1ot7$1@dont-email.me>
Bytes: 5459

On Tue, 2024-06-04 at 16:14 +0200, immibis wrote:
> On 3/06/24 16:22, wij wrote:
> > If =E2=84=99=3D=E2=84=95=E2=84=99, which means the remaining task can b=
e completed independently in Ptime
> > without I. In this sitution, solve_remain(q2,I) is equivalent to temp_a=
np(q2).
> > But the complexity of computation is W(|q|)=3DW(|q|-1)+ W(|q|-1)=3D 2^(=
|q|-1)*W(1),
> > a O(2^N) level of complexity contradicting he assumed Ptime. Therefore,=
 =E2=84=99=E2=89=A0=E2=84=95=E2=84=99.
>=20
> If I understand it correctly, you think that if an algorithm for solving=
=20
> a problem takes O(2^N) complexity then the problem can't be P-time.
>=20
> But this is not correct. There are slow algorithms for fast problems.=20
> For example, if I know a binary number M, and I want to calculate=20
> whether all binary numbers with the same number of bits are less than or=
=20
> equal to M, I could do it by looping through all the binary numbers with=
=20
> the same number of bits, and checking if each one is less or equal. That=
=20
> would be an O(2^N) algorithm. Or, I could think about the problem for a=
=20
> bit, and then check whether all the bits in M are 1. That would be an=20
> O(N) algorithm. Since there is an O(N) algorithm, it is a P-time problem=
=20
> - even though an O(2^N) algorithm exists as well.

The proof was modified in more detail:
....
.... See the link (same as above)
....
Prop1: ANP problem can be divided into two size-1-subproblems.
   Proof: By spliting the certificate as follow:
          bool temp_anp(Problem q) {
            if(q.certificate().size()<Thresh) { // Thresh is a small consta=
nt
              return solve_thresh_case(q);
            }
            Problem q1,q2;
            split_certificate(q,q1,q2);        // Split the certificate in =
q
            return temp_anp(q1) || temp_anp(q2); // to form q1,q2
          }

Prop2: =E2=84=99=E2=89=A0=E2=84=95=E2=84=99
   Proof: The temp_anp(q) can be re-written as follow:
          bool temp_anp(Problem q) {
            if(q.certificate().size()<Thresh) { // Thresh is a small consta=
nt
              return solve_thresh_case(q);
            }
            Problem q1,q2;
            split_certificate(q,q1,q2);  // Split the certificate in q to
                                         //   disjoint subproblem q1, q2.
            Info I;                      // I=3Dinfo. that helps solving q
            if(temp_anp_i(q1,I)=3D=3Dtrue) { // temp_anp_i(q1,I) solves tem=
p_anp(q1)
                                         // and stores whatever helpful int=
o I
              return true;
            }
            return solv_remain(q2,I);    // Solve temp_anp(q2) with the giv=
en I
          }

          For a =E2=84=95=E2=84=99=E2=84=82 problem q, if =E2=84=99=3D=E2=
=84=95=E2=84=99, then information I is unnecessary for
          solv_remain(q2,I) because it can compute I in Ptime by its own. T=
hus,
          the complexity of solv_remain(..) is equivalent to the independen=
t
          size-1-subproblem temp_anp(q2) (if not equivalent, the general
          recursive algorithms of solving =E2=84=95=E2=84=99=E2=84=82 and P=
rop1 are wrong, which is not
          the fact). Equally, temp_anp_i(q1,I) is then equivalent to the
          size-1-subproblem temp_anp(q1) simply by not providing I. Therefo=
re,
          the complexity of temp_anp(q) is W(|q|)=3D W(|q|-1)+W(|q|-1)=3D
          2^(|q|-1)*W(1), W(1)>=3D1, a O(2^N) level of complexity contradic=
ting
          the assumed Ptime. Therefore, from =E2=84=95=E2=84=99=E2=84=82=E2=
=89=A0=E2=84=99, we can conclude =E2=84=99=E2=89=A0=E2=84=95=E2=84=99.
---------------------------------------------------------------------------=
--

If I understand your question correctly, if solv_remain(q2,I) can be comput=
ed
in Ptime ANYWAY, that will lead to say that any problem in =E2=84=95=E2=84=
=99 can be Ptime
reduced to a dummy-fixed-time problem... that would be another 'humiliating=
'=20
proof. The proof above is more 'constructive' in that the method is resuabl=
e=20
(hopefully) to analyse other problems and conquer searching problems.