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

[fresh_42]

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 ...

 

[Jarvis323]

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$.

 

[fresh_42]

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.

 

[Jarvis323]

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).

 

[fresh_42]

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.)

 

[fresh_42]

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!

 

[Jarvis323]

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.