Subject: RE: Theology warning! (was: Re: [hackers-il] RE: Re: Concrete and Abstract Stuff...)

From: Chen Shapira <[email-masked]>
Date: Wed, 6 Mar 2002 14:28:32 +0200

> An interesting question is, can we do the morphing in O(1)?

I believe you can, given enough graduate students.

---

From: Ofir Carny <[email-masked]>
Date: Wed, 6 Mar 2002 09:38:02 +0200

AFAIRemeber, NP-completness definition requires that any mechanisms which
solves one member solves in a polynomial overhead all. Thus such an oracle
can be e.g. something which can satisfy an arbitrary logic formula (e.g.
a&&b||c) in polynomial time. A infinite-dimesional tank genetic computer
comes to mind.

-----Original Message-----
From: Omer Zak [mailto:[email-masked]]
Sent: Wednesday, March 06, 2002 9:11 AM
To: [email-masked]
Subject: Theology warning! (was: Re: [hackers-il] RE: Re: Concrete and
Abstract Stuff...)

On 6 Mar 2002, Oleg Goldshmidt wrote:

> "Nadav Har'El" <[email-masked]> writes:
[... snipped ...]
> > The course Technion course "complexity theory" talks quite a bit
> > (among a lot of other things) about what you can achieve (and what
> > you cannot acheive) by adding oracles to a turing machine (e.g.,
> > oracles with NP power, oracles with oracles with NP power, and ad
> > inifinitum). It's an interesting, but very abstract and quite
> > difficult, course.
> 
> Since I never took such a course, I am curious: is there a Universal
> NP-complete Oracle?

Tsk, tsk!  Are you asking if there is a God?
                                             --- Omer
There is no IGLU Cabal.  History records series of bloody and messy 
religious wars at sites of attempts to start IGLU Cabals.
WARNING TO SPAMMERS:  see at http://www.zak.co.il/spamwarning.html

To unsubscribe from this group, send an email to:
[email-masked]

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

---

From: Ofir Carny <[email-masked]>
Date: Wed, 6 Mar 2002 11:33:27 +0200

You really should be interested in doing the morphing in O(Poly) rather than
O(1).

-----Original Message-----
From: Oleg Goldshmidt [mailto:[email-masked]]
Sent: Wednesday, March 06, 2002 10:25 AM
To: [email-masked]
Subject: Re: Theology warning! (was: Re: [hackers-il] RE: Re: Concrete
and Abstract Stuff...)

> Tsk, tsk!  Are you asking if there is a God?

No. I am asking if there is an Oracle. Note that it is not equivalent
to asking if there is a Larry Ellison. ;-)

All NP-complete problems are equivalent, so I am asking whether there
is a (gedanken) Oracle that can solve all of them. One way to
construct such an oracle is to build an oracle to solve one
NP-complete problem, e.g. finding Hamiltonian circuits, in O(1), and
an algorithm to morph all other NP-complete problems into that one.
An interesting question is, can we do the morphing in O(1)?

Well, it's all (partly) tongue-in-cheek...

-- 
Oleg Goldshmidt | [email-masked] 
Only wimps use tape backup: real men just upload their important 
stuff on ftp, and let the rest of the world mirror it. [L. Torvalds]

---

From: Ofir Carny <[email-masked]>
Date: Thu, 7 Mar 2002 14:59:42 +0200

If you really want to play god - solve the general halting problem in O(1)
(or solve it at all)

-----Original Message-----
From: Nadav Har'El [mailto:[email-masked]]
Sent: Thursday, March 07, 2002 1:35 PM
To: [email-masked]
Subject: Re: Theology warning! (was: Re: [hackers-il] RE: Re: Concrete
and Abstract Stuff...)

On Wed, Mar 06, 2002, Omer Zak wrote about "Re: Theology warning! (was: Re:
[hackers-il] RE: Re: Concrete and Abstract Stuff...)":
> The point that this particular oracle (the NP-complete oracle) is
> equivalent to the way God is described in monotheistic religions (God who
> knows all and is present everywhere).

Actually, NP languages are not in any sense the class of most complicated
problems imaginable, so being able to solve them doesn't make you God :)

Some people somehow got the impression that "NP" means "non-polynomial",
but of course it doesn't: NP means "non-deterministic polynomial" - the
class
of languages that can be recognized by a non-determinstic turing machine
(which has a very specific and not very intuitive definition).

There are bigger (actually nobody knows if they're really bigger, but at
least
they are not smaller) classes like PSPACE, the class of languages that can
be recognized by a deterministic turing machine with polynomial memory
requirements (and no bound on the computation time).

So an NP-complete oracle is not omnipotent. If P!=NP (nobody has proven this
yet... It's the biggest open problem in this area), Adding an NP-complete
oracle to P gets you one step closer to PSPACE. Adding an oracle of this new
type to NP gets you another step, and so on. This is known as the
"polynomial
hierarchy". If I remember correctly, nobody yet knows if the polynomial
hierarchy ends in PSPACE, whether it gets to PSPACE in 1 step, 7 steps, or
an infinite amount of steps. Complexity theory is filled with open
questions...

> More probably in O(N) time.  But even O(N^100) would be very good deal.

Actually, I don't think that you can do better than saying "polynomial
time", with possibly a different exponent for different NP languages.

P.S. As usual, please correct me if I've made some embarassing mistakes
in the theory...

-- 
Nadav Har'El                        |       Thursday, Mar 7 2002, 23 Adar
5762
[email-masked]
|-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |I want to be a human being, not a human
http://nadav.harel.org.il           |doing -- Scatman John