Decidable?
From: Srivasta R. (vatsa.at.cisco.com)
Date: 01/22/04
- Next message: Richard Heathfield: "Re: Mars Rover Controlled By Java"
- Previous message: JTK: "Re: Mars Rover Controlled By Java"
- Next in thread: Michael J. Fromberger: "Re: Decidable?"
- Reply: Michael J. Fromberger: "Re: Decidable?"
- Reply: Michael N. Christoff: "Re: Decidable?"
- Reply: Mitch Harris: "Re: Decidable?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Thu, 22 Jan 2004 10:30:32 +0530
Hello,
I am trying to solve the following problem:
+- {0} if P=NP
|
L = +
|
+- {1} otherwise.
Is L decidable?
I tend to think that L is undecidable since a TM can't decide if P=NP. I
saw one similar post in this group, but I was not convinced with the
explanations posted. Can someone tell me whether my analysis of the
problem is correct or not.
Thanks in advance,
Srivatsa
-- ----------------------- Srivatsa R. Iyengar Cisco Systems, India. Web: http://www.cisco.com Ph: 2299625x3882 ---------------------- There are 10 types of people in this world... those who understand binary and those who don't.
- Next message: Richard Heathfield: "Re: Mars Rover Controlled By Java"
- Previous message: JTK: "Re: Mars Rover Controlled By Java"
- Next in thread: Michael J. Fromberger: "Re: Decidable?"
- Reply: Michael J. Fromberger: "Re: Decidable?"
- Reply: Michael N. Christoff: "Re: Decidable?"
- Reply: Mitch Harris: "Re: Decidable?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]