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

AI Thread Summary
The discussion centers on the complexity of calculations, specifically the P vs. NP conjecture, and the role of Turing Machines (TMs) in understanding computational problems. It emphasizes the need for precise definitions of calculations and complexity, noting that a calculation involves a problem, a computer, and a result. Participants suggest clarifying that a TM's execution is parameterized by the problem instance, with polynomial algorithms applicable to specific instances. The conversation also highlights the theoretical nature of TMs, comparing them to computer programs and stressing that simplifications in explanations can lead to imprecision. Overall, the thread aims to provide a clear overview of P vs. NP for those unfamiliar with the topic.
fresh_42
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
2024 Award
Messages
20,627
Reaction score
27,770
This article deals with the complexity of calculations, and in particular the meaning of $$P\stackrel{?}{\neq}NP.$$ Before we explain what ##P## and ##NP## actually are, we have to solve a far bigger problem: What is a calculation? And how do we measure its complexity? Many people might answer, that a calculation is an algebraic expression and its complexity the number of additions, subtractions, multiplications and divisions. However, isn't a division more complex than an addition? Isn't it strange, that we did not use the words \textit{problem} or \textit{result}? And what if we decided to differentiate or integrate? It becomes clear that we need better tools and a preciser language if we want to make all these terms rigorous. The task is clear
$$
\text{ Problem } \;\longrightarrow \; \text{ Computer } \;\longrightarrow \;\text{ Result }
$$
We need an alphabet to write the problem, a computer to do the calculations, and a decision whether we achieved a result or not. Everybody who ever mistakenly wrote an endless loop knows that the last part is not trivial. Let's start with an example with true and false. This should easily fit into our scenario.

Continue reading ...
 
Last edited:
  • Like
Likes Jarvis323 and Greg Bernhardt
Technology news on Phys.org
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
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.
 
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).
 
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:
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!
 
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.
 
Back
Top