3 ms·

I tried to settle a Millenium problem with ChatGPT: Is P = NP ? > No, P is not equal to NP. P (polynomial time) is a subset of NP (nondeterministic polynomial

by tromp 4y ago

I tried to settle a Millenium problem with ChatGPT: Is P = NP ? > No, P is not equal to NP. P (polynomial time) is a subset of NP (nondeterministic polynomial time), meaning that there are certain problems that can be solved in polynomial time that cannot be solved in nondeterministic polynomial time. Good start, although one should say P is conjectured to be not equal to NP. Some serious misunderstanding in that last part though.

tylerchurch 4y ago
Similar oddities with the halting program. Prompt: Write a program that never halts. > It is not possible to write a program that never halts. All programs will eventually halt, or terminate, once they have completed the instructions given to them. This is known as the halting problem, and it has been proven to be unsolvable. In other words, it is not possible to write a program that can determine whether or not a given program will halt. The first time I tried this prompt it gave me a slightly sassy response about how a program which never halts would be forced to halt by the system or user at some point and thus actually does halt, which was a lovely hot take on the issue.
- ncallaway 4y ago
  Yea, the halting problem is easy if you’re allowed to use the heat death of the universe in your answer…
layer8 4y ago
Interesting. It’s giving me a better answer: P vs. NP is a well-known problem in computer science and mathematical complexity theory. P is the class of problems that can be solved quickly by a computer, while NP is the class of problems for which a solution can be verified quickly by a computer. The question of whether P equals NP is one of the most important open problems in computer science. Many experts believe that P does not equal NP, but this remains unproven. With your answer, I’d have asked it for an example of a problem that can be solved in polynomial time but cannot be solved in nondeterministic polynomial time.

by tromp 4y ago

tylerchurch 4y ago

Similar oddities with the halting program. Prompt: Write a program that never halts. > It is not possible to write a program that never halts. All programs will eventually halt, or terminate, once they have completed the instructions given to them. This is known as the halting problem, and it has been proven to be unsolvable. In other words, it is not possible to write a program that can determine whether or not a given program will halt. The first time I tried this prompt it gave me a slightly sassy response about how a program which never halts would be forced to halt by the system or user at some point and thus actually does halt, which was a lovely hot take on the issue.

ncallaway 4y ago
Yea, the halting problem is easy if you’re allowed to use the heat death of the universe in your answer…

layer8 4y ago

Interesting. It’s giving me a better answer: P vs. NP is a well-known problem in computer science and mathematical complexity theory. P is the class of problems that can be solved quickly by a computer, while NP is the class of problems for which a solution can be verified quickly by a computer. The question of whether P equals NP is one of the most important open problems in computer science. Many experts believe that P does not equal NP, but this remains unproven. With your answer, I’d have asked it for an example of a problem that can be solved in polynomial time but cannot be solved in nondeterministic polynomial time.