P = NP, undecidable?
PT
undecidable? It seems possible - an infinite set,
involving a question of computation.
Also, suppose a polynomial time algorithm existed,
and was discovered. Is it possible that this fact, i.e.
that it always runs in polynomial time, might be undecidable?
Of course, empirically we would measure its performance,
but might that be unprovable?
---
Paul T.
robert...@yahoo.com
> I wonder if the P = NP problem might be Godel
> undecidable? It seems possible - an infinite set,
> involving a question of computation.
Seems unlikely - that would imply that if a polynomial time algorithm
for an NP complete problem existed, we could not discover it.
Zhu Guohun
> Also, suppose a polynomial time algorithm existed,
> and was discovered. Is it possible that this fact, i.e.
> that it always runs in polynomial time, might be undecidable?
> Of course, empirically we would measure its performance,
> but might that be unprovable?
>
undecidable problem as an NP problem on TM?
----------------
Zhu
dj3v...@csclub.uwaterloo.ca.invalid
We haven't had much success at that so far.
dave
--
Dave Vandervies dj3vande at eskimo dot com
>If you're going to flame somebody, get it right.
He did.
--Chris Dollin roasts a troll in comp.lang.c
robert...@yahoo.com
> In article <5ed16cf5-4065-4e18-b4af-5df89cbcc...@59g2000hsb.googlegroups.com>,
>
> robertwess...@yahoo.com <robertwess...@yahoo.com> wrote:
> >On Aug 5, 6:43 pm, PT <ptanenb...@consultant.com> wrote:
> >> I wonder if the P = NP problem might be Godel
> >> undecidable? It seems possible - an infinite set,
> >> involving a question of computation.
>
> >Seems unlikely - that would imply that if a polynomial time algorithm
> >for an NP complete problem existed, we could not discover it.
>
> We haven't had much success at that so far.
Sure, but if P?=NP is undecidable, it means we have to be able to
prove that we cannot discover a polynomial time algorithm for a NP
complete problem, even if it does exist, even with a oracle. Seems
unlikely.
Of course most people would be stunned to find that P=NP.
Phlip
>>> undecidable? It seems possible - an infinite set,
>>> involving a question of computation.
>>
>> Seems unlikely - that would imply that if a polynomial time algorithm
>> for an NP complete problem existed, we could not discover it.
>
> We haven't had much success at that so far.
That civilians are allowed to know about...
4N
"Zhu Guohun" <ccg...@hrt.dis.titech.ac.jp> ha scritto nel messaggio
news:145e131a-32e7-4524...@r15g2000prh.googlegroups.com...
> Also, suppose a polynomial time algorithm existed,
> and was discovered. Is it possible that this fact, i.e.
> that it always runs in polynomial time, might be undecidable?
> Of course, empirically we would measure its performance,
> but might that be unprovable?
>
if you find an algorithm that runs in polinomial time than the machine stops
always after a certain number of operations that depends on the data in
input, so of course it's decidible.... or did I get something wrong?
Alan Morgan
robert...@yahoo.com <robert...@yahoo.com> wrote:
>On Aug 5, 6:43=A0pm, PT <ptanenb...@consultant.com> wrote:
>> I wonder if the P =3D NP problem might be Godel
>> undecidable? =A0It seems possible - an infinite set,
>> involving a question of computation.
>
>
>Seems unlikely - that would imply that if a polynomial time algorithm
>for an NP complete problem existed, we could not discover it.
Couldn't it also mean that we could discover a polynomial time
algorithm but would be unable to prove it runs in polynomial time?
Alan
--
Defendit numerus
Alan Morgan
Yes. It's entirely possible that the program might run in super polynomial
time for some data sets (the ones you didn't test, of course) or that it
actually runs in super polynomial time but the constant factors make it
look like polynomial time for small data sets or it might be really
frickin' hard to analyze (see the Miller-Rabin primality test, which runs
in polynomial time if the GRH is true. Step 1: Prove GRH. Or read up on
Pairing Heaps). You can't prove generalities by testing specifics.
Alan
--
Defendit numerus
robert...@yahoo.com
> Couldn't it also mean that we could discover a polynomial time
> algorithm but would be unable to prove it runs in polynomial time?
Sort of a programmatic version of FLT (until Wiles a few years ago, of
course)? Perhaps, but I think you'd then have to prove that any
solution you could discover would be polynomial time for all case you
could ever hope to test, but was unprovable in the general case. To
continue the analogy with FLT, you’d have to prove that FLT was true
for any tuple (a, c, b, n) you could test, but that it was not true in
general – IOW, that there was some tuple that you could not test (and
that would be a case that disproves FLT). Seems unlikely.
Wolf Kirchmeir
Seems to me that we wouldn't know that it was a polynomial time algorithm.
--
wolf k.
Alan Morgan
Wolf Kirchmeir <ElLob...@ruddy.moss> wrote:
>Alan Morgan wrote:
>> In article <5ed16cf5-4065-4e18...@59g2000hsb.googlegroups.com>,
>> robert...@yahoo.com <robert...@yahoo.com> wrote:
>>> On Aug 5, 6:43=A0pm, PT <ptanenb...@consultant.com> wrote:
>>>> I wonder if the P =3D NP problem might be Godel
>>>> undecidable? =A0It seems possible - an infinite set,
>>>> involving a question of computation.
>>>
>>> Seems unlikely - that would imply that if a polynomial time algorithm
>>> for an NP complete problem existed, we could not discover it.
>>
>> Couldn't it also mean that we could discover a polynomial time
>> algorithm but would be unable to prove it runs in polynomial time?
>
Of course not, that's the beauty of it! But the fact that we don't know
that it is a polynomial time algorithm doesn't mean that it isn't one.
OTOH, what this requires is not just an algorithm for which we do not know
the runtime (of which we have several instances today), but an algorithm
for which we can not know the runtime. I'm really not sure that such
an animal exists (Goodstein Sequence?).
Alan
--
Defendit numerus
PT
huh?
---
Paul T.
PT
> > >> I wonder if the P = NP problem might be Godel
> > >> undecidable? It seems possible - an infinite set,
> > >> involving a question of computation.
>
> > >Seems unlikely - that would imply that if a polynomial time algorithm
> > >for an NP complete problem existed, we could not discover it.
>
> prove that we cannot discover a polynomial time algorithm for a NP
> complete problem, even if it does exist,
No, it means:
i) there does not exist such an algorithm,
i.e. P /= NP
or
ii) an algorithm does exist, but we cannot prove
it works (in polynomial time) for every case. Which
does seem bizarre, I wonder if that is possible?
---
Paul T.
4N
"PT" <ptane...@consultant.com> ha scritto nel messaggio
news:344d726c-a34a-47f2...@v1g2000pra.googlegroups.com...
he was talking about turing machines.
Aatu Koskensilta
> I wonder if the P = NP problem might be Godel
> undecidable? It seems possible - an infinite set,
> involving a question of computation.
P = NP might well be undecidable in any of the formal theories usually
considered to formalise the commonly accepted mathematical principles,
in the theoretical sense that there is no logical result ruling out
this possibility.
> Also, suppose a polynomial time algorithm existed, and was
> discovered. Is it possible that this fact, i.e. that it always
> runs in polynomial time, might be undecidable?
Yes. That is, there is no logical necessity to an algorithm being
polynomial time being formally provable in this or that formal
theory. Using standard techniques we can concoct artificial examples,
e.g. an algorithm that given input x checks whether x is a proof of a
contradiction in a theory T, and if so, goes on and calculates
something that takes 2^x^x^x^x^x^...^x steps, and if not, just
stops. For the relevant (consistent) theories T the fact that this
algorithm runs in polynomial time is not provable, since from that the
consistency of T, which is not provable in T by the second
incompleteness theorem, follows.
--
Aatu Koskensilta (aatu.kos...@uta.fi)
"Wovon man nicht sprechen kann, darüber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
Chris Menzel
<aatu.kos...@uta.fi> said:
> PT <ptane...@consultant.com> writes:
>
>> I wonder if the P = NP problem might be Godel undecidable? It seems
>> possible - an infinite set, involving a question of computation.
>
> P = NP might well be undecidable in any of the formal theories usually
> considered to formalise the commonly accepted mathematical principles,
> in the theoretical sense that there is no logical result ruling out
> this possibility.
>
>> Also, suppose a polynomial time algorithm existed, and was
>> discovered. Is it possible that this fact, i.e. that it always runs
>> in polynomial time, might be undecidable?
>
> Yes. That is, there is no logical necessity to an algorithm being
> polynomial time being formally provable in this or that formal theory.
> Using standard techniques we can concoct artificial examples, e.g. an
> algorithm that given input x checks whether x is a proof of a
> contradiction in a theory T, and if so, goes on and calculates
> something that takes 2^x^x^x^x^x^...^x steps, and if not, just stops.
> For the relevant (consistent) theories T the fact that this algorithm
> runs in polynomial time is not provable, since from that the
> consistency of T, which is not provable in T by the second
> incompleteness theorem, follows.
cute
Zhu Guohun
If you want to prove that the P = NP is undecidable with an
existance undecidable polynomial time algorithm such as $L$, you
must prove that $L$ belongs to NP,.
In additional, even you can find an undecidable polynomial time
algorithm , but this algorithms do not belong to P or NP, then you can
not prove that P=NP is undecidable.
For instance, no one can prove that the halting problem belong to NP
as I known, thus P=NP is decidable even the the halting problem is
undecidable.
----------------------------
Zhu
PT
> > I wonder if the P = NP problem might be Godel
> > undecidable? It seems possible - an infinite set,
> > involving a question of computation.
>
> P = NP might well be undecidable in any of the formal theories usually
> considered to formalise the commonly accepted mathematical principles,
> in the theoretical sense that there is no logical result ruling out
> this possibility.
>
> > Also, suppose a polynomial time algorithm existed, and was
> > discovered. Is it possible that this fact, i.e. that it always
> > runs in polynomial time, might be undecidable?
>
> Yes. That is, there is no logical necessity to an algorithm being
> polynomial time being formally provable in this or that formal
> theory. Using standard techniques we can concoct artificial examples,
> e.g. an algorithm that given input x checks whether x is a proof of a
> contradiction in a theory T, and if so, goes on and calculates
> something that takes 2^x^x^x^x^x^...^x steps, and if not, just
> stops. For the relevant (consistent) theories T the fact that this
> algorithm runs in polynomial time is not provable, since from that the
> consistency of T, which is not provable in T by the second
> incompleteness theorem, follows.
Clever. However, this example is not too convincing,
as it involves issues of proof and consistency, which
are known undecidable.
In the NP problem, each specific input is finite and
decidable (though the domain of possible inputs is
infinite). The issue involves determining the time
required for solution.
So for a candidate algorithm, one must show:
i) it terminates
ii) it computes the correct solution
iii) it runs in polynomial time
Intuitively, this seems feasible, but of course
we need something stronger than intuition.
I would like to see a counter-example, or argument,
more comparable to the NP problem than the one
you offered.
> "Wovon man nicht sprechen kann, darüber muss man schweigen"
> - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
Old Ludwig was well acquainted with Usenet, apparently...
---
Paul T.
george
> > discovered. Is it possible that this fact, i.e. that it always
> > runs in polynomial time, might be undecidable?
This question is mis-phrased. The original askers were using
"undecidable" as though it were a unary predicate. It isn't..
Whether anything is or isn't undecidable depends on WHAT AXIOMS
you are trying to decide it FROM.
> Yes. That is, there is no logical necessity to an algorithm being
> polynomial time being formally provable in this or that formal
> theory.
But the point is, it ISN'T "this or that" formal theory.
The RELEVANT formal theory is a STRONG one, strong ENOUGH
to prove these KINDS of results IN GENERAL!
> Using standard techniques we can concoct artificial examples,
Can you use Rice's theorem to concoct natural examples?
That is normally about partial recursive functions, but can you
restrict to total?
ica...@gmail.com
I would like to propose another conjectural solution to P=NP problem.
It is well known that three-colorability problem of planar graphs is
in NP class.
But I can say that (conjecture) for at least this problem that there
exists sequence of unrelated linear algorithms
A_1,A_2,...,A_k, k>1 such that output of A_i is an input of A_(i+1),
i=1,2,...,k-1 such that A_k solves the NP class problem efficiently.
The above suggestion comes from my non-computer proof of the four
color theorem by spiral chains.
In this solution the first linear alogorithm A_1 is construction of
spiral chains in the maximal planar graph and the next linear
algorithm A_2 is the spiral chain coloring of the union of spiral
chains found in A_1. Hence for this case k=2. Of course four coloring
is not in NP. But I wonder if my method can be used for the 3-coloring
problem of the planar graphs.
More you can find about the spiral chain coloring algorithm at:
http://www.flickr.com/photos/49058045@N00/2372086534/
Cahit