P vs. NP conjecture and what is a Turing Machine (TM)?

In summary: So, I get that you want to keep it simple and not mention TMs at all.In summary, the conversation discusses the P vs NP problem, which asks whether there is a polynomial-time algorithm for solving NP-complete problems. The discussion touches on the use of Turing machines as a theoretical model for computation, and the concept of parameterized algorithms that take input instances as parameters. The conversation also mentions the importance of distinguishing between instances, elements, sets, and classes in mathematical descriptions. Overall, the conversation aims to give a simplified overview of the P vs NP problem for readers who may have heard of it elsewhere.
Technology news on Phys.org
  • #2
Good overall presentation of P vs NP. I think a few parts could possibly use improvement.

Instead of describing an execution of a TM given an input as an algorithm, I would suggest to specify that the algorithm is parameterized by the problem instance (basically the TM itself is the algorithm, its execution and runtime depends on the initial tape input). And instead of ##D## being a set of problems, one problem has a set of instances, and you have one polynomial algorithm which takes instances ##x \in D## as input parameters. It is polynomial time, ##O(n^c)## over all ##x##, where ##n## is the length of ##x##.
 
Last edited:
  • Like
Likes Chikitai and fresh_42
  • #3
Jarvis323 said:
Good overall presentation of P vs NP. I think a few parts could possibly use improvement.

Instead of describing an execution of a TM given an input as an algorithm, I would suggest to specify that the algorithm is parameterized by the problem instance (basically the TM itself is the algorithm, its execution depends on the initial tape input). And instead of ##D## being a set of problems, one problem has a set of instances, and one polynomial algorithm which takes an instance ##x \in D## as an input parameter must decide all instances. It is polynomial time, ##O(n^c)## , where ##n## is the length of ##x##.
I took it mostly from a book for applications. I avoided the tour to formal languages and Chomsky which IMO is a better-suited framework than decidability problems. Anyway, the language I have chosen is far from perfect, but a better summary would have required a lot more technical descriptions which I tried to avoid. I think ##I\in D =_{e.g.} 2-SAT \ni \{\text{ my 2 examples }\}## explains enough of what I mean. The mathematical challenge was to distinguish instances, elements, sets, and classes.

Nobody will ever consider actually using a TM, so it's irrelevant whether an algorithm is the TM itself or just a certain initial configuration. I think setting both equal is misleading. A TM is a theoretical model that can harbor many initial configurations aka algorithms.
 
  • #4
fresh_42 said:
Nobody will ever consider actually using a TM, so it's irrelevant whether an algorithm is the TM itself or just a certain initial configuration. I think setting both equal is misleading. A TM is a theoretical model that can harbor many initial configurations aka algorithms.

Basically, a specific TM is a akin to a specific computer program (the program could be considered an implementation of an algorithm). The parameters are set through the contents of the input tape. A universal TM is one which simulates other TMs (like an operating system which runs other programs).
 
  • #5
Jarvis323 said:
Basically, a specific TM is a akin to a specific computer program (the program could be considered an implementation of an algorithm). The parameters are set through the contents of the input tape. A universal TM is one which simulates other TMs (like an operating system which runs other programs).
Ok, can be done. The problem was really to give an overview for people who hear or read P vs. NP somewhere. It was more or less the answer to all the mess and misconceptions in
https://www.physicsforums.com/threads/p-vs-np-and-godel.1016942/
I thought I should explain it in a language as common and easy as I can. Students of Computer Science have hopefully better sources than PF. However, with every simplification, every comparison, and every omitted formula comes an imprecision. I basically summarized 30 pages in the book. That cannot be done without losses. The more as the title was "... für Anwender" Sorry, I have no idea what an Anwender is in English. (And no, it is not 'user', 'experimatlist', or 'engineer'. It's from all of them a bit plus something that those words do not cover. It literally means applicator.)
 
Last edited:
  • #6
Jarvis323 said:
Good overall presentation of P vs NP. I think a few parts could possibly use improvement.

Instead of describing an execution of a TM given an input as an algorithm, I would suggest to specify that the algorithm is parameterized by the problem instance (basically the TM itself is the algorithm, its execution and runtime depends on the initial tape input). And instead of ##D## being a set of problems, one problem has a set of instances, and you have one polynomial algorithm which takes instances ##x \in D## as input parameters. It is polynomial time, ##O(n^c)## over all ##x##, where ##n## is the length of ##x##.
Before I forget it again: Thanks for your careful read!
 
  • Like
Likes Jarvis323
  • #7
fresh_42 said:
Ok, can be done. The problem was really to give an overview for people who hear or read P vs. NP somewhere. It was more or less the answer to all the mess and misconceptions in
https://www.physicsforums.com/threads/p-vs-np-and-godel.1016942/
I thought I should explain it in a language as common and easy as I can.

Yeah, I get that. The CS theory professor I learned from basically first established that you can implement any algorithm with a TM (Church- Turing Thesis), and then that modern computer languages are Turing complete, and after that, you can ignore the details of TMs and just think in terms of computer programs in your favorite language if it helps.
 

1. What is the P vs. NP conjecture?

The P vs. NP conjecture is a fundamental problem in computer science that deals with the complexity of solving certain types of problems. It asks whether every problem whose solution can be quickly verified by a computer can also be solved quickly by a computer.

2. What is the significance of the P vs. NP conjecture?

The answer to the P vs. NP conjecture has major implications for fields such as cryptography, artificial intelligence, and optimization. A proof that P = NP would mean that problems that are currently considered difficult or impossible to solve could be solved efficiently, revolutionizing many industries and fields.

3. What is a Turing Machine (TM)?

A Turing Machine (TM) is a hypothetical computing device that was proposed by Alan Turing in the 1930s. It is a simple model of a computer that consists of a tape, a read/write head, and a set of rules that dictate how the head moves and modifies the tape according to the input it receives.

4. How does the concept of a TM relate to the P vs. NP conjecture?

The P vs. NP conjecture is closely related to the concept of a TM because it deals with the ability of a computer to solve problems. TMs are used to represent algorithms and their efficiency, so understanding the capabilities of a TM can help us understand the limitations of computers in solving certain types of problems.

5. Is the P vs. NP conjecture solved?

No, the P vs. NP conjecture is still an open problem in computer science. Many attempts have been made to prove or disprove it, but so far, no one has been able to provide a conclusive answer. It remains one of the most intriguing and challenging problems in the field of computer science.

Similar threads

  • Programming and Computer Science
Replies
29
Views
2K
  • Programming and Computer Science
Replies
2
Views
698
  • Programming and Computer Science
Replies
4
Views
2K
  • General Math
Replies
2
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Differential Equations
Replies
1
Views
646
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
2K
Replies
33
Views
5K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
5K
Back
Top