- #1
- 19,761
- 25,763
Last edited:
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.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##.
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.
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 inJarvis323 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).
Before I forget it again: Thanks for your careful read!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##.
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.
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.
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.
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.
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.
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.