P = NP? With bonus brain uploading

justsomeguy1984

Registered
Joined
Mar 20, 2019
Messages
2
Reaction score
0
I'm writing a sci-fi story about a mathematician.

He explains the P versus NP problem such that computers can solve some problems (P) and people are needed to solve others (NP). So he merges man and machine and uploads his brain into a computer, expecting that with enough time (computer cycles) he'll be able to figure out the problems that no person or computer could solve on their own. Of course this causes issues, or problems, of its own.

My questions:

* If brain-uploading is possible in this story, does the rest of the idea check out?
* Is there anything I'm missing in the complexities of P and NP?

Thanks for reading. I am new to this forum and very grateful for your time and knowledge.
 

Introversion

Pie aren't squared, pie are round!
Kind Benefactor
Super Member
Registered
Joined
Apr 17, 2013
Messages
10,643
Reaction score
14,867
Location
Massachusetts
I think you’re asking, “Is this plausible?”

I’m not sure it matters. “Do readers enjoy it?” is the important question. Vast swaths of spec-fic use plot-devices that violate known physics and/or math, but are highly entertaining.

You should try to be consistent with whatever handwavium you use, but other than that, go for it.
 

justsomeguy1984

Registered
Joined
Mar 20, 2019
Messages
2
Reaction score
0
Thank you! Plausibility is part of the question, but I was also wondering if that brief summary was accurate enough to the real P versus NP problem. I've been doing a good bit of research, though I'm just not sure that my mental model of it is anywhere close to a what a studied mathematician's or computer scientist's might be.
 

Introversion

Pie aren't squared, pie are round!
Kind Benefactor
Super Member
Registered
Joined
Apr 17, 2013
Messages
10,643
Reaction score
14,867
Location
Massachusetts
I assume you've seen definitions of P vs NP like this one?

https://en.wikipedia.org/wiki/P_versus_NP_problem

Wikipedia said:
The informal term quickly, used above, means the existence of an algorithm solving the task that runs in polynomial time, such that the time to complete the task varies as a polynomial function on the size of the input to the algorithm (as opposed to, say, exponential time). The general class of questions for which some algorithm can provide an answer in polynomial time is called "class P" or just "P". For some questions, there is no known way to find an answer quickly, but if one is provided with information showing what the answer is, it is possible to verify the answer quickly. The class of questions for which an answer can be verified in polynomial time is called NP, which stands for "nondeterministic polynomial time".

An answer to the P = NP question would determine whether problems that can be verified in polynomial time can also be solved in polynomial time. If it turned out that P ≠ NP, which is widely believed, it would mean that there are problems in NP that are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.

I think your challenge is not going to be whether "P = NP" is actually true, but writing something that readers care about. Most readers won't care what P and NP mean. Or whether it's plausible that a human thinking at computer speeds could solve this better than computers. If the protagonist has stakes, and there's relatable tension around those, it probably doesn't matter hugely what the plot-devices are?
 

lizmonster

Possibly A Mermaid Queen
Absolute Sage
Super Member
Registered
Joined
Jul 5, 2012
Messages
14,537
Reaction score
24,107
Location
Massachusetts
Website
elizabethbonesteel.com
Thank you! Plausibility is part of the question, but I was also wondering if that brief summary was accurate enough to the real P versus NP problem. I've been doing a good bit of research, though I'm just not sure that my mental model of it is anywhere close to a what a studied mathematician's or computer scientist's might be.

How many of those people are going to be your readership?

How much of the story depends on your accurate understanding of the problem?

You're already positing impossibilities (the "uploading" of a person into a computer). That doesn't mean you toss reality completely, but for something like P = NP - which is currently still under a lot of discussion in various disciplines - I think you're fine with a story that says "Here's a guy who's solved it (or thinks he's solved it), and now X happens."
 

WeaselFire

Benefactor Member
Kind Benefactor
Super Member
Registered
Joined
May 17, 2012
Messages
3,539
Reaction score
429
Location
Floral City, FL
Let's see, several thousand human brain in a computer stories out there, many people like. Yep, it's possible and plausible.

I think you're either overthinking this or you haven't done enough research. If this is the entire premise of your story, time to start digging through the scholarly research. If it's just a part of your story, explain it and go on.

By the way, the P/NP discussion has been going on for a century or more. The NP side keeps getting smaller... :)


Jeff
 
Last edited:

relletyrots

The One Who Tells The Story
Super Member
Registered
Joined
Aug 25, 2017
Messages
198
Reaction score
39
Location
Mostly inside my own head.
Computer scientist here. I agree with some of the sentiments of the other replies; indeed, most of your readership will probably glance over any statements about P vs. NP and take your word for it, at least as the problem pertains to your story. And generally speaking, I am more on the side that favors storytelling over fact (when that is necessary.) However, I'll try to give you my impression of your ideas as someone who studied the subject, because I appreciate attention to detail, and because I believe that knowing what you're writing about, even if you don't use that knowledge explicitly, can give you a better feel for the underlying ideas and result in a better story.

He explains the P versus NP problem such that computers can solve some problems (P) and people are needed to solve others (NP).
Honestly, this is the first time I'm encountering such a definition of P and NP. Now, obviously, this is not a rigorous definition and it isn't intended to be, but it also gives the wrong impression that humans are somehow related to the mathematical objects P and NP. To be clear, humans play no role in complexity theory. However, I can kind-of see where you want to go with this, and it might work. In a way. I'll talk about exactly how in a bit.

Is there anything I'm missing in the complexities of P and NP?
I could go into the precise definitions in layman's terms, but that'd be long and probably unhelpful. So I'll try and be concise: P is the set of problems that can be solved in a reasonable time by computers, while NP is the set of problems that can be verified in a reasonable time by computers. Let's for now think about a problem as a question that one needs to answer. If it's in P, that means that there is a fast algorithm that can answer that question. If it's in NP, that means that there is a fast algorithm which, given an answer, can tell you if that answer is correct. Again, questions in P can be answered easily, but for questions in NP, you are only guaranteed that any answer can be checked easily. But where do you get the answer from? That might take a long long time to compute.

That's where you might want to insert "human intuition." Maybe there's something special about our brains, that allows us to arrive at solutions without fully understanding how we got there? That allows us to pull answers from the ether, and then we only need to check them? Personally, I don't buy it, but that besides the point.

Think about Sudoku, for example. It might take a long time to solve, so it's not necessarily in P. But if someone presents you with a solution, it's very easy to check that the solution is correct. (In fact, you guessed it, Sudoku is NP-complete.) But maybe, somehow, human intuition can help us solve Sudoku efficiently if combined with a computer?

If brain-uploading is possible in this story, does the rest of the idea check out?
Personally, I think the main attraction of mind-uploading is not necessarily proving P=NP (it has nothing to do with that), but with being able simulate human brains (a form of AI) much faster than you an I can think. Imagine the progress that can be made by AI's that think 1000 times faster than us. This is not about breaking some complexity barrier, complexity hasn't got much to do with it. This is about speeding up intellectual progress. In a year you can get the same progress it would take humanity 1000 years to achieve (so, yeah, maybe then the AI's would have already figured out P vs. NP?)

So, forgive the detours, and let me lay out exactly in what way I think this might work. I see basically two ways forward:
(1) As I said, uploading human minds and speeding them up may yield a proof for P=NP, simply by having human minds working on it for long. That proof may very well include a way to solve any problem quickly, which is basically what you want from proving P=NP, I guess.
(2) One may claim that the solution for P vs. NP was in the human mind all along. How? Well, the way to show P=NP is to show that any problem that can be checked quickly, can also be solved quickly. But there's an easier way. NP-completeness tells us that really, you only need to show that one problem can be solved quickly, and maybe the solution to such a problem can be achieved by running the human mind more efficiently. Such problems are called NP-complete problems, and there are several of them known (like Sudoku), but obviously none of them are known to be in P. Your mathematician may have found a way to solve an NP-complete problem by combining brains and machines, which would indeed prove P=NP. (That could never happen in reality, but who cares.) By the way, the concept of NP-completeness is a pretty incredible thing, if you care to get into it, but it might be too technical for the story, idk.

Oh, another thing you might want to consider. If P=NP, then something called the Hierarchy Collapse will occur. (Dramatic, isn't it?) This is basically the collapse of the Polynomial Hierarchy, which is something even more profound than P=NP, albeit much less well-known to the public. It would mean that pretty much any question that you can ask can be answered quickly (well, kinda, but again, who cares.) Honestly, just the name Hierarchy Collapse sounds cool.

Anyway, I wrote a lot, and I hope I helped. And again, like the others said, put your story and readers first, fact second. After all, P=NP is a pretty radical statement to make in our world, but it's completely acceptable in yours.
 
Last edited:

onesecondglance

pretending to be awake
Kind Benefactor
Super Member
Registered
Joined
May 2, 2012
Messages
5,359
Reaction score
1,661
Location
Berkshire, UK
Website
soundcloud.com
relletyrots said:
Personally, I think the main attraction of mind-uploading is not necessarily proving P=NP (it has nothing to do with that), but with being able simulate human brains (a form of AI) much faster than you an I can think. Imagine the progress that can be made by AI's that think 1000 times faster than us. This is not about breaking some complexity barrier, complexity hasn't got much to do with it. This is about speeding up intellectual progress. In a year you can get the same progress it would take humanity 1000 years to achieve (so, yeah, maybe then the AI's would have already figured out P vs. NP?)

If you have an AI with thought processes exactly like a human, it'll get distracted a thousand times quicker too...

(The more serious point being that human thought is not at all like a computer program.)
 

relletyrots

The One Who Tells The Story
Super Member
Registered
Joined
Aug 25, 2017
Messages
198
Reaction score
39
Location
Mostly inside my own head.
If you have an AI with thought processes exactly like a human, it'll get distracted a thousand times quicker too...
True, but evidently, humans make progress in spite of their imperfect attention span.

(The more serious point being that human thought is not at all like a computer program.)
The reason that this is true may very well be that we just don't know how to write such a computer program yet. As someone who knows the field, we are not anywhere close to getting AGI (artificial general intelligence), but once we do, human thought might very well be just another kind of computer program. Actually, the fact that, as you say, "human thought is not at all like a computer program", is exactly why AI research exists, and why AGI's would be so groundbreaking (and possibly terrifying if they got out of hand.) But unless you believe in some external soul, or believe some version of biological panpsychism, we are just a machine, and our mind is just its hard-wired program. (Of course, we are a machine crafted by evolution over billions of years, but still.)

(Edited: changed "hard-coded" to "hard-wired".)
 
Last edited:

onesecondglance

pretending to be awake
Kind Benefactor
Super Member
Registered
Joined
May 2, 2012
Messages
5,359
Reaction score
1,661
Location
Berkshire, UK
Website
soundcloud.com
I largely agree, except with the statement about "machines". You might not mean this at all, but often this imagery of bodies being hardware, and the mind being software, is used to reinforce the idea of body/mind duality: that the mind is somehow shackled by the body and can be "set free". I prefer a view of embodied cognition: thought is intertwined with the physical, so we are talking more about firmware at best, and in reality, a class of programming that, as you say, does not exist yet.
 

relletyrots

The One Who Tells The Story
Super Member
Registered
Joined
Aug 25, 2017
Messages
198
Reaction score
39
Location
Mostly inside my own head.
I largely agree, except with the statement about "machines". You might not mean this at all, but often this imagery of bodies being hardware, and the mind being software, is used to reinforce the idea of body/mind duality: that the mind is somehow shackled by the body and can be "set free". I prefer a view of embodied cognition: thought is intertwined with the physical, so we are talking more about firmware at best, and in reality, a class of programming that, as you say, does not exist yet.

Oops, I meant hard-wiring, not hard-coding. (Edited.)

And I completely agree. You're right, I probably used the words "machine" and "program" a bit recklessly here, but that is basically what I meant when I said (or meant to say) hard-wired program. Truly, if we want to be precise, any of the familiar terms we use for computers might be way too artificial and completely inappropriate to describe beings that are the result of evolution, and not the construction of concept-oriented humans. Evolution just wants us to work, it doesn't care if our composition is in any way intelligible.



(Nonetheless, I probably stand by my metaphor, as nothing more than a metaphor, since there is a sense in which our "machines" are similar in fundamental elements and general structure, but differ in minute details of "hard-wiring". That said, I agree that it's inaccurate, and I'm for embodied cognition all the way.)
 
Last edited: