I solved the P versus NP problem, one of the Millennium Prize Problems

[c910335]

I am here to announce that I successfully proved P=NP, and thus I solved the P versus NP problem, one of the Millennium Prize Problems.

So here is the proof:

The following code solves the subset sum problem, one of the NP-complete problems, in only constant time (immediately).

answer? // true

unco subset_sum(multiset: Int[], target: Int, i: Int = -1, sum: Int = 0) => {
   i++!
   if (i == multiset.size) return false!
   sum += multiset[previous i]!
   return (
      sum == target ||
      subset_sum(multiset, target, i, sum) ||
      subset_sum(multiset, target, i, previous sum)
   )!
}

const const answer<-Infinity> = subset_sum([771, 121, 281, 854, 885, 734, 486, 1003, 83, 62], 2640)!

Since the subset sum problem is an NP-complete problem, any algorithm solving it in polynomial time (and I did it in constant time) implies P=NP.■

Actually, with the powerful lifetime feature of DreamBerd, we can solve any NP probrem, any PSPACE problem, any EXPTIME problem, any ELEMENTARY problem, or even any decidable problem immediately. This is WAY MORE POWERFUL than any computer in the world or even any quantum computer humans will make in the future.

DreamBerd is indeed a world-changing invention.

Note: The example input is taken from The Easiest Hard Problem Note: I didn't actually solve the P versus NP problem because the DreamBerd abstract machine is not Turing-equivalent. Even if it actually solves any NP-complete problem in polynomial time, that does not imply P=NP. Note: unco (a subsequence of function) is うんこ, which is poop in Japanese. Note: I hope that my code is correct.

[TodePond]

congrats! This one would be a great one to add to examples. want to submit a PR?

[ktlknss]

I think i have made it more efficient, not sure tho, needs more testing

uni pVsNp( // ai should solve this

[MikeyBeez]

https://github.com/MikeyBeez/millennium-p-vs-np.