Tfw too intelligent to believe in P = NP

We don't care about what you believe or not.
P=NP is a mathematical problem. As such, we will only care if you present a correct, rigorous solution.
Until then, your opinion is worth nothing.

>mfw the axioms constructing P=NP are incoherent

>tfw two intelligent too disprove your disproval.

>Writting a proof is as hard as checking it
I don't think so, in fact almost no-one with higher education in math/compsci believes that P=NP

>tfw to intellegently too waste time on you are trivial abstractions

I did some googling after user pointed out that master anti-brainlet Knuth believed that P = NP.

First off, this is taking some liberties, because he says that he's more in favor of the possibility, which doesn't mean he believes it.

Secondly Knuths argument is interesting. Essentially he says that since the only requirement to be in P is that your running time is n^c for some c, and since there are so many possible algorithms in the space up to arbitrarily large c, it's hard to believe that there is NO single algorithm in this space.

It's not a super convincing argument, and also he mentions that it could be n^^^^^^^^arbitrarily large constant, which effectively is intractible except pedantically (that is to say, it's not intractible by formal definition)

can it be thought of as a provable space and an unprovable space?

Why not divide both sides by P so that N=1 ?

I strongly suspect P != NP, however it wouldn't be the first time people have been wrong.

...

How can it be argued that P != NP? Once an unsupervised hard AI is cranking out algorithms it will be P = NP. To argue P != NP is to argue there will never be hard AI.

You have a shallow understanding of both AI and algorithms.

But to humor you, most people who study algorithms feel that there is an inherent difficulty presented in NP-complete problems. This comes from the combinatorial explosion most of these problems experience as n increases. Since you can reduce any problem in NP to a problem in NP-complete consider TSP.

TSP has n! possibilities at each move in the search space. How can you come up with an algorithm which only depends on n^c where c is some constant completely independent on n while returning the correct exact answer?

It's also not unreasonable to posit there will never be "hard" AI in the theoretical sense, although empirical results will surely become more refined.

This is true, although that is not a valid response to my arguement, regardless of how shallow it may be. When I refer to hard AI I mean to say sentient AI, not several machine learning algorithms back propagating and feeding algorithms foward. Sentient AI is fundementally emulated neurology, Sentient AI could solve and prove problems in polynomial time. A sentient AI could potentially work out new mathematical concepts to make every problem P = NP, is this correct? Or does the current literature of mathematics fill the book ends?

I mean, if you assume a "Sentient AI" which can "solve and problem in polynomial time" is a possible thing, then sure.

I think most people would also agree that this isn't possible however.

Also, if a machine can solve a problem in polynomial time, that doesn't mean the problem is a polynomial problem.

For example, you could have a hypothetical machine which has a table of all solutions to every possible instance of TSP. Then the machine solves TSP in O(1) time, but TSP is not a constant time problem.

Another example, you could have a more realistic machine which is just very very fast, maybe using some quantum computing ideas or some other technology not quite in our reach. This machine simple brute force searches the space for solutions to TSP. Perhaps it can accomplish it in a second, that doesn't make TSP polynomial.

Its unreasonable to assert that hard AI is unreasonable. Do you posit a soul is essential to cognition? If not, what aspect of the brain cannot be throughly emulated down to an atomic level? Given we will likely never see a hard AI in our lives, perhaps not in the next 500 years, but to assert its impossibility is an erroneous position.

No, it's perfectly reasonable. Derailing into materialism vs idealism isn't something I intend to do though. I hope my expositions helped you understand a bit more.

Another view which might help you see the argument:

Even if we have an "agent" with unbounded capabilities, can it derive an algorithm for something which is impossible?

Can it find a sorting algorithm which runs in constant time? (No, we have proven lower bounds).

So there's nothing about advancing AI which has anything to do with P vs NP except that many AI problems are very hard in and of themselves.

Humans currently perform closer to P=NP than computers. A computer with several hundred times the neuronal capacity of the human brain could certainly yield P=NP, even if it has to develop a new system of mathematics to achieve that. Just as integral calculus was developed to calculate the area around curves, a new system could be developed to calculate the ideal route between points to make a closed loop, and do so as quickly as if it was checking the answer.
Its reasonable to assert that there is a metaphysical aspect to the human brain? Thats absurd. You can probably find some hugs over at though.

I hate the arguments in this thread. P=NP is a very simple problem relating to how fast you can manage the doubling of complexity in a problem. The algorithm has a clear shape, easily visualized as a copying pyramid symmetric about the middle. The fact no one even uses the word symmetric in this thread is why you are all so fucking shit. None of you have any intuition or understanding into the reality of the space or question. Last I talked about it I got called schizo so fuck off.

P=NP definitely true.

Why does P vs. NP attract so many laymen and schizos?

this and only this is the fucking answer

P=NP

P/P = NP/P

N = 1

P(1) = P

P = P

Wheres my million dollars?

If the human brain is some sort of computer and can solve a simple NP problem then P=NP, right?

I gave you so many simple illustrations but the crux of the problem is that you literally have no idea what P vs NP even means.

can you tell me what P vs NP means then?

Educate yourself.

u probably have a simple CS explanation of P vs NP and that's not what i'm talking about

Trying to hide the fact that you're retarded by projecting huh?

...

Prove it then, explain what P vs NP is. In a non-"simple CS explanation"

is P isomorphic to NP i.e.
epi and mono
maybe just left amenable

Lol...

i could go on, but you seem like don't believe in 42

very original

This is taking precisely no liberties. The requirement for P = NP is that there exists a polynomial-time algorithm for some NP-complete problem. Practical tractability has nothing to do with the problem formulation; if there exists a n^c algorithm, c=1000000000, for an NP-complete problem, P = NP.

No, it was taking liberties because Knuth doesn't believe P = NP but is slightly in favor of it.

Simply changing the wording of the problem doesn't show you have any appreciation for it, which is demonstrated by your previous posts.

It's also better to think of the problem in terms of sets instead of an isomophic relation since if P = NP then P and NP are trivially isomorphic via the identity mapping....

>Simply changing the wording of the problem doesn't show you have any appreciation for it, which is demonstrated by your previous posts.

also, has different semantics, not just terms.
i may not have the classical appreciation for it.
i personally don't give a fuck about polynomial time. it's just not my style.

It's also better to think of the problem in terms of sets instead of an isomophic relation

>why set?
elements in a set have no context with other elements in the set. an relationship gives context.

>if P = NP then P and NP are trivially isomorphic via the identity mapping....

Nope.jpg
maybe for a later time

Because P is a subset of NP by definition.

If you don't care about the subject why are you posting ignorance and then bitching about it?

The problem is literally formulated as a question of if NP is a subset of P, since P is a subset of NP. Jesus christ. I'm so triggered. lmao

What more can you expect of somebody who is genuine about being a computer scientist? You can have your hunches and tend towards certain opinions, but nobody serious is going to be like, 'NOPE. P NOT NP. 100%,' or the opposite.

This also doesn't change the fact that you can be an educated, active, and productive computer scientist and still feel that P may equal NP. This directly contradicts an earlier post in this thread: "no one who has studied algorithms believes that P = NP you fucking retard"

Can you go ahead and tell us what it means for an element to be in the set P? What does it mean for an element to be in the set NP?

it's right up your ass, try grabbing it out

Isn't P polynomial time and NP is not polynomial time?

not that guy btw but how would p be a subset of np

NP is nondeterministic polynomial time.

Informally, NP is the set of problems that can be verified in polynomial time. P is obviously a subset of NP since if you can solve the problem itself in polynomial time you can verify a solution in polynomial time (by solving it and comparing answers).

haha yea man incoherent haha yea man good claims haha xD

>tell someone CH is independent of current axioms of set theory
>they say they are going to solve it.

But if you think of human brain as a box of heuristics, it really isn't performing closer to P=NP in a universal sense

Please stop, that user obviously had NO IDEA what he was talking about.

facts are facts

Well, no. A sufficiently advanced AI can't force P=NP when it's not. It could prove whether P=NP though

Could it? Or are you yet another essentially popsci dreamer here to talk about hypothetical AI.

Know anything about AI? Automated theorem proving? Hell, too much to ask but, complexity classes?

I am very interested in automated theorem proving

What is a programming language which is popular for ATP? Why is this the case (what proof system does the language implement)?

If you can answer this I will *possibly* believe you.

much like the fucking OP

>you're
>intelligence

>believe
thats not how science works son

Someone explain this in the most easy way possible.

let imagine that we know you're a brainlet. We aren't sure if you're seriously retarded or not, but we can't prove that you're only a brainlet and not seriously retarded.

So we conclude that you're autistic.

P ? NP

Well you'd have a problem because maybe P = 0

is finding a solution to a problem as easy as checking whether the solution is correct

I really don't like this explanation because the term "easy" doesn't mean what it means in real life.

>What is a programming language which is popular for ATP

SML ML Twelf

> what proof system does the language implement

are you talking about the what logical framework?

>tfw I solved P=NP a long time ago but like seeing idiots scratch their heads

P = NP
(P)/P = (NP)/P
1 = N
N = 1, P = P

retards

No but I will believe you.

I was talking about Prolog which implements an extended version of SLD-resolution.

>signs are pointing towards P != NP
We don't even have a lower bound of n^2 for 3-sat smart guy.

The truth is there is no sign. Honestly Knuth argument about how Robertson-Seymour theorem gave a surprising cubic algorithm to recognize a minor free class of graph makes as much sense as anything I've heard toward P!=NP