Deutsch English Français Italiano |
<92bfb07b264dbfa64c9866e2243e8cd09de4909e.camel@gmail.com> View for Bookmarking (what is this?) Look up another Usenet article |
Path: ...!2.eu.feeder.erje.net!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: How to prove q is not NPC? Date: Tue, 30 Jul 2024 20:29:15 +0800 Organization: A noiseless patient Spider Lines: 11 Message-ID: <92bfb07b264dbfa64c9866e2243e8cd09de4909e.camel@gmail.com> References: <e6c84e13457b182991801bb2c50463354dff0b6b.camel@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Injection-Date: Tue, 30 Jul 2024 14:29:16 +0200 (CEST) Injection-Info: dont-email.me; posting-host="bc2446965c1a268f25118957b9eb4a17"; logging-data="1094233"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18yC9IzpKGzDTfnbt3YGaQg" User-Agent: Evolution 3.50.2 (3.50.2-1.fc39) Cancel-Lock: sha1:ssxDjXti91T+R8GvonvpFomWjkg= In-Reply-To: <e6c84e13457b182991801bb2c50463354dff0b6b.camel@gmail.com> Bytes: 1381 On Mon, 2024-07-29 at 07:00 +0800, wij wrote: > Problem q: Given a number n, determine whether n is 5 or not. > What is the VALID proof that q=E2=88=89NPC? >=20 > !!! This is a challenging question !!! >=20 Let's change the question a bit. How do you prove q is not a NPC problem?