[ 3 / biz / cgl / ck / diy / fa / ic / jp / lit / sci / vr / vt ] [ index / top / reports ] [ become a patron ] [ status ]
2023-11: Warosu is now out of extended maintenance.

/sci/ - Science & Math

View post   
File: 23 KB, 414x255, p-versus-np.png [View same] [iqdb] [saucenao] [google]
2716899 No.2716899 [Reply] [Original]

/sci/, prove to me once and for all that P = NP, or that it does not.

>> No.2717030,1 [INTERNAL] 

>>2717029
>Your "significantly" more info is mostly irrelevant, though. So you have to sort through all the useless crap to find an answer (much like one would blindly have to go through and start dividing a big ass number by primes in hopes that they cleanly divide it).

Oh, wow, that's so much bullshit, you've even decided to delete it.

>> No.2716911

P = NP only if N = 1

Since N stands for not, and not is represented by 0, then P /= NP.

>> No.2716917

>P = NP only if N = 1
or if P = 0 and N arbitrary.

Know your computer science, brah.

>> No.2716926

>>2716917
I thought P and N were vectors though.

>> No.2716923

Do your own homework CS undergraduate from the future!

>> No.2716932

>>2716911
>Since N stands for not
>N stands for not

>mfw non-deterministic = not

>> No.2716933

>>2716926
Are you daft? The P = NP wouldn't make sense with vectors.

Maybe if P were a vector and N were a matrix.

>> No.2716945

>>2716933
Doesn't vector multiplication produce a vector? I thought N was the identity vector <1,1,1>.

>> No.2716956

How can you expect to P = NP ?
Imagine prime factorization

If you have say 3*11*17 you know very easily that the answer is 561

If I give you 561 and ask for the number of primes and their values, you have to do some sort of process to find out the extra information that is missing. You have way more information in the first scenario than the second. How could you expect them to both be solved at the same rate when factoring requires significantly more effort just to get to an equal footing to just multiplying?

>> No.2716978

>>2716956
>implying anybody cares about your intuitive bullshit arguments

>> No.2716994

>>2716945
>vector multiplication

You talking about vector product? That produces a pseudovector, thus equating it to a vector is bound to screw your shit up.

>> No.2716995

I feel the overwhelming need to mention that peoples keyboards should have a negation symbol.
P=¬P

>> No.2716997

>>2716994
No, I meant what I said

>> No.2717005

>>2716956
How can you expect to P = P ?
Imagine efficient route planning.

If you have say third left, 8th right, 5th left you can easily verify that it's less then 2 km.

If I give you an upperbound of 2 km and ask for a sufficiently short route, you have to do some sort of process to find out the extra information that is missing. You have way more information in the first scenario than the second. How could you expect them to both be solved at the same rate when route planning requires significantly more effort just to get to an equal footing to just following a route?

Fucking shortest routes, how do they work?

>> No.2717008

>>2716995
d'accord. What's the unicode for that?

æ hehehe

>> No.2717011

>>2716995
Read: >>2716932
2/10

>> No.2717018

OP, that's like saying apple = napple. It makes no sense.

troll elsewhere.

>> No.2717021

>>2716997
What's a "vector multiplication" then?

>> No.2717030

>>2717011
I know, but it just looks untidy like that. Mileage varies I guess.

>> No.2717029 [DELETED] 

>>2717005
Your "significantly" more info is mostly irrelevant, though. So you have to sort through all the useless crap to find an answer (much like one would blindly have to go through and start dividing a big ass number by primes in hopes that they cleanly divide it).

>> No.2717054

>>2717021
isn't it when you bend the two together?

>> No.2717056

>>2717029
>Your "significantly" more info is mostly irrelevant, though. So you have to sort through all the useless crap to find an answer (much like one would blindly have to go through and start dividing a big ass number by primes in hopes that they cleanly divide it).

Oh, wow, that's so much bullshit, you've even decided to delete it.

>> No.2717079

>>2717054
Give me the multiplication rule, damn it. I want equations, not words, since apparently you use nonstandard names for stuff.

>> No.2717096

>>2717056
Figured it was the courteous thing to do since it was in complete contradiction to your post. Not bullshit. The problem in both scenarios is too many degrees of freedom for the NP side providing the need for one to reduce it to only relevant info.

Your P = P just threw me off. That and complete yanking of how everything was typed. Take it as you will

>> No.2717095

>>2717021
Fucking cross products, how do they work?

>> No.2717105

>>2717095
He just said it's not a cross product, which I was talking about in >>2716994.

>> No.2717108

>>2717096
You know that shortest path finding is a polynomial problem right?

>> No.2717131

>>2717108
http://en.wikipedia.org/wiki/Travelling_salesman_problem
>The Travelling Salesman Problem (TSP) is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science.

What are you talking about?

>> No.2717140

>>2717131
>implying TSP is the same thing as Shortest Path

>> No.2717146

>>2717131
Traveling salesman is more difficult. Shortest-path you're trying to get from A to B while minimizing cost. Traveling salesman means you have to hit ALL the cities without repeats, minimizing cost.

>> No.2717150

>>2717131
>What are you talking about?
Dijkstra's algorithm, bitches.

>> No.2717165

>>2717131
After you read:
>>2717140
>>2717146
>>2717150
Go and read:
>>2717005
again, and then your:
>>2716956

Do you now understand why this argument is bullshit?

>> No.2717187

>>2716899
>implying P = NP is not undecidable in ZFC

>> No.2717203

>>2717187
Is it? Why? Linky?

>> No.2717206

>>2717203
It might be, but it certainly isn't known to be so.

>> No.2717220

>prove something that the greatest mathematicians there are cannot prove despite the fact you're all 12 year olds

>> No.2717227

>>2717220
No one in this thread even tried, except for this retard (>>2716956). His status is [x]fucking told.

>> No.2717239

>>2717227
I'm sure half the people in the past have tried and failed in the past. I know I have, several times.

>> No.2717282

>>2717239
Point is, we're not arrogant enough to post our tries on a board.
We're in the 2nd stage of ignorance. We know we don't know.

>> No.2717331

>>2717165
http://en.wikipedia.org/wiki/Shortest_path_problem
>shortest path problem is the problem of finding a path between two vertices (or nodes) such that the sum of the weights of its constituent edges is minimized.

For the shortest path problem you add up all the weight combinations and pick the smallest number. It takes one go through to consider all possibilities

http://en.wikipedia.org/wiki/Longest_path_problem
>Finding the shortest simple path on a graph with negative-weight cycles is therefore also NP-complete

Shortest path becomes an NP problem the moment you allow negative weights (going back). The ability to go back causes an exponentially higher number of possible paths for the same number of nodes.

Is this all correct?

It is the same (yet again) as prime factorization. If you were given the list of primes that are less than a given number, then you would have P time (right?). You would just have to divide each prime into the number until all options are exhausted.
If you are not told the prime numbers, (you don't have positive weights) then you take much longer because you have to find the relevant values (just like you have to throw out the shitty weights that backtrack you).

Does this not make sense?

>> No.2717363

Here's the latest proof that P=NP:

http://www.optimization-online.org/DB_FILE/2011/02/2920.pdf

Excercise: Find an error, it's not that hidden.

>> No.2717382

>>2717331
>For the shortest path problem you add up all the weight combinations and pick the smallest number. It takes one go through to consider all possibilities
No, you do not consider all combinations, as there are an exponential number of combinations.

>Shortest path becomes an NP problem the moment you allow negative weights (going back).
Going back is not negative weight, you fucking retard.
>Is this all correct?
NO

In the shortest path problem you are allowed to travel backwards over edges. Compare negative weights to a street that takes -5 minutes by car. Yes, that is indeed impossible.

>> No.2717405

>>2717363
No time to read. Did he O(n), instead of O(digits of n)?

>> No.2717435

>>2716956

it's not whether P does or does not equal NP.

It's about proving it either way

>> No.2717436

>>2717405
Possibly, but I didn't finish either. I stopped after finding the first error, which is almost as obvious.