P vs NP and a finite number of sybmols?
From: Casey Hawthorne (caseyh_at_istar.ca)
Date: 04/25/04
- Next message: Tim Smith: "Re: How difficult is the firing squad synchronization problem?"
- Previous message: Michael Mendelsohn: "Re: A CFG for a CFL"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Sun, 25 Apr 2004 17:52:54 GMT
Is the essence of P vs NP that NP machines use an exponential number
of symbols (Turing machines - another one for each branch in the
computation) to see if there is one accepting state?
Therefore: there would not be a proof of P != NP using a finite number
of symbols?
Regards,
Casey
- Next message: Tim Smith: "Re: How difficult is the firing squad synchronization problem?"
- Previous message: Michael Mendelsohn: "Re: A CFG for a CFL"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]