[ 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: 198 KB, 407x559, GodfreyKneller-IsaacNewton-1689.jpg [View same] [iqdb] [saucenao] [google]
6133919 No.6133919 [Reply] [Original]

So what do you guys thinks is the hardest of the remaining ones?


1.1 P versus NP
1.2 The Hodge conjecture
1.4 The Riemann hypothesis
1.5 Yang–Mills existence and mass gap
1.6 Navier–Stokes existence and smoothness
1.7 The Birch and Swinnerton-Dyer conjecture

>each is worth fame and a US$1,000,000 prize

>> No.6133922

>P versus NP

this is one is hardcore

>> No.6133937

I don't even get P vs NP. Usually with those problems the wiki page is full with formulas one doesnt even get unless one studies math. but p vs np is mostly text. yet i dont understand it.

>> No.6133945

>>6133937
i guess most agree it's the hardest one

I can't even grasp it completely

>> No.6133956

>>6133937
>>6133945
Google NP-Complete Problem
Solve problem with an algorithm whose time is O(x^n) (where x is related to the number of things in the problem, and n is a constant not related to x).
Receive million dollars.

>> No.6133968

are those problems even 100% solvable?

>> No.6133972

>>6133968
we gotta try

>> No.6133981

>>6133972
i have to know before i dedicate my life to solving them

>> No.6133984

>>6133981
then you will never solve them.

>> No.6133986

>>6133981
Prove that its unsolvable, you would probably still get the prize.

>> No.6134005

>>6133986
>>6133984
if i did solve them, then what?

do i call some center and they bring me in to prove it?

>> No.6134018

>>6134005
contact whoever is offering the prize. Im sure contacting the institutes are easier than solving any of these problems.

>> No.6134021

>>6134005
>A proposed solution to one of the Millennium Prize Problems may not be submitted directly to CMI for consideration.

>Before consideration, a proposed solution must be published in a refereed mathematics publication of worldwide repute (or such other form as the SAB shall determine qualifies), and it must also have general acceptance in the mathematics community two years after.

http://www.claymath.org/millennium/Rules_etc/

>> No.6134024

>>6134021
fucking gatekeepers, always keeping the common man down.

>> No.6134027

>>6134021

that's gay

>> No.6134032

P = NP is trivial just divide by P.

The hodge conjecture makes me really hard because it makes me think about calvin and hobs

>> No.6134039 [DELETED] 

tfw I solved the pointcare conjucture but didnt get the money because the russian fucker solved it a month before me

and he didnt even take the money. why couldnt I have it then? ;_;

>> No.6134050

>>6133919
they should raise the prize money. one million dollars doesn't seem like much for what the solution is worth.

>> No.6134057

>>6134021
>TWO YEARS
>GETTING INTO A FAMOUS MAGAZINE
yeah, not happening

fuck it

>> No.6134059

does solving a millenium problem also automatically grant you a fields medal?

>> No.6134080

>>6133919
P vs. NP.
pretty common consensus, plus if you look at the problem it's even more intractable than the others.

>> No.6134085

>>6133981
given how you are behaving in this thread I doubt you will solve it anyways.

>> No.6134091

>>6134024
>>6134027
>>6134057
ITT: complete fucking idtiots.

>> No.6134090

>>6134080
>plus if you look at the problem it's even more intractable than the others

That doesn't even mean anything

>> No.6134092

>>6134050
they don't have the money. that's why. plus you get basically any job you want.

>> No.6134098

>>6134059
why do you care?
not officially, at least. but the fame alone is enough. All you'd get with a fields medal is fame anyways.

>> No.6134122

Just glancing over them the hardest to me seems like Yang Mills, you would need greater resources and more experience in a lot of different fields compared to the rest of them

>> No.6134144

>>6134122
whats the easiest one?

>> No.6134148

Bunch of computer scientist talking shit in this thread. Riemann is the deepest problem left unsolved.

>> No.6134154

Shall we try together /sci/ maybe start with the obvious,
The P versus NP problem is a major unsolved problem in computer science. Informally, it asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer. It was introduced in 1971 by Stephen Cook in his seminal paper "The complexity of theorem proving procedures"[2] and is considered by many to be the most important open problem in the field.[3] It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute to carry a US$1,000,000 prize for the first correct solution.

The informal term quickly used above means the existence of an algorithm for the task that runs in polynomial 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 may be possible to verify the answer quickly. The class of questions for which an answer can be verified in polynomial time is called NP.

>> No.6134166

>>6134154
>problem in computer science
> it asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer.
>The informal term quickly used above means the existence of an algorithm for the task that runs in polynomial time. The general class of questions for which some algorithm can provide an answer in polynomial time is called "class P" or just "P"
1. A mechanical device capable of processing all of the systems given information at one instance to Judge the computers action in the given task
2. IN that being said an algorithm has to be created that can interpret and judge the next action.

any one wanna correct me so far?

>> No.6134174

>>6134091
explain

>> No.6134192

I don't think P = NP matters.

I think it's rather obviously false that P means "tractable" in any significant way.

Complexity theory a shit.

>> No.6134208

didn't' some Russian mathematician recluse solve one of the Clay math problems? I think he refused the prize too!

>> No.6134210

>>6134192
>I don't think P = NP matters.

it doesn't since you can assume either way and go on with your research but it would be neat to PROVE it.

>> No.6134214

P vs NP Problem
Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker's list also appears on the list from the Dean's office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.

>> No.6134215

>>6134192
>I think it's rather obviously false that P means "tractable" in any significant way.

This. Outside of OR (and even inside it) the impact will be minor or nonexistent

>> No.6134219

https://en.wikipedia.org/w/index.php?title=P_versus_NP_problem&oldid=580113483#P_.3D_NP

Basically nothing happens if P=NP even with a good algorithm for SAT

>> No.6134228

>>6134148
Can you expand on that? What makes you judge the Riemann hypothesis as so much deeper than P versus NP? Deeper than the other ones I won't dispute, but P=NP doesn't seem any less fundamental than the Riemann hypothesis to me.

>> No.6134236

>>6134228
How the hell is P=NP fundamental at all?

Riemann hypothesis implies a fuckton of results about the primes and number theory

>> No.6134243

GOD TIER DIFFICULTY
Hard problem of qualia

High tier
P=NP
Riemann Hypothesis

Mid tier
Yang-Mills Existence and mass gap

Low tier
Navier-Stokes
The Birch and Swinnerton-Dyer conjecture

>> No.6134247

>>6134243
they all pay the same so who gives a fuck

>> No.6134249

>>6134243
>qualia
>>>/x/

>> No.6134252

>>6134243
>High tier
>P=NP
>Low tier
>Navier-Stokes

retard detected

>> No.6134256

guys why don't we solve one of these all together and split all the prize money?

>> No.6134254

>>6134236
It's ultimately the question of whether trying to prove something is fundamentally a different process than checking whether a given proof is correct. If P=NP, then they are basically the same operation, and proving things is something that can efficiently be done fully automatically. If P!=NP, as everyone thinks, they are fundamentally different, and the former doesn't reduce to the latter without introducing an exponential factor.

>> No.6134259

Wasn't P=NP supposedly solved awhile ago. I remember seeing a thread on it here? Did that turn out to be bogus?

The supposed answer was no.

>> No.6134260

>>6134236
>Riemann hypothesis implies a fuckton of results about the primes and number theory

P=NP is million times more valuable though.

>> No.6134267

>>6134254
>If P=NP, then they are basically the same operation, and proving things is something that can efficiently be done fully automatically

Proving theorems is not only not in NP but it's also UNDECIDABLE. You can't automate theorem proving retard.

>>6134260
not really

>> No.6134272

>>6134267
Yes really. If you could prove that P=NP and show how one NP program is equivalent to all other ones and could devise an algorithm for it, you could become a multi-billionaire in no time.

>> No.6134271

>>6134267
Not in propositional logic it ain't.

>> No.6134277

>>6134271
propositional logic is just SAT. You can't write all theorems in terms of it

>>6134272
>and show how one NP program is equivalent to all other ones and could devise an algorithm for it

that's already been done

>> No.6134278

>>6134272
>become a multi-billionaire in no time
highly doubt it

>> No.6134280

>>6134267
http://en.wikipedia.org/wiki/Automated_theorem_proving

>> No.6134281

>>6134267
>not really
If P=NP, the other five remaining millennium prize problems will in all likelihood be solved within a week.

>> No.6134291

>>6134281
retard

>>6134280
https://en.wikipedia.org/wiki/Automated_theorem_proving#Decidability_of_the_problem

>> No.6134296

>>6134277
>propositional logic is just SAT. You can't write all theorems in terms of it
You can write all theorems in propositional logic in terms of it. For most more powerful logics you'll need more powerful techniques. Yes, the problem is usually undecidable in full generality, but computing whether there is a proof *of reasonable length* of some proposition in first-order logic is in NP. If P=NP, for all intents and purposes, this would mean mathematics is SOLVED.

>> No.6134301

>>6134281
>If P=NP, the other five remaining millennium prize problems will in all likelihood be solved within a week.

see >>6134219
> Special emphasis must be placed on the assumption that the proof exists within a "reasonable" size as proving arbitrary sized proofs of mathematical statements is not in NP and in fact are not even decidable. The assumed size of the formal proof being check must be quite small as even a n^3 algorithm looking for a proof of only 1MiB in size could take tens of thousands of years to complete.

>> No.6134316

>>6133919

P vs. NP, then Riemann hypothesis

>> No.6134318

>>6134278
Well, you obviously know fuck-all about CS and optimization industry and what people would pay big money for. Stay clueless.

>> No.6134322

>>6134318
No one would pay shit for a n^100 3-SAT algorithm

>> No.6134339

>>6134214
This doesn't look like a difficult problem. Just run through the list picking students as you go, skipping any that are ineligible.

Either you missed something or I did.

>> No.6134346

>>6134339
yeah, you missed this
>the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe

>> No.6134358

>>6134346
I get that, but it seems you need to form only one set, not sort through all of them.

>> No.6134361

>>6134339
>>6134358
The problem itself is quite terribly worded and really long to read. Here's one that's easier to wrap your head around: "You have a set of integers, positive and negative. Determine if you can choose a subset of them (no repeats) such that they sum to 0."

Sounds easy, right?

>> No.6134364

>>6134214
The human mind is a biological computer.

Because of this, any problem that can be solved by a human must be able to be solved by a computer.

>> No.6134368

>>6134361
That sounds hard. Thanks for explaining.

>> No.6134386

>>6134368
>That sounds NP hard.

ftfy

>> No.6134391

>>6134364
So is that the answer?

Where is my $1,000,000

>> No.6134394

>>6134361
What would it mean for this particular problem to be reducible to polynomial time?

>> No.6134401

>>6134394
To be specific, how must the problem be reducible? I don't quite understand what it means to be "solvable in polynomial time".

>> No.6134405

>>6134391
P vs NP is a question of how easy it is for a computer to search for the solution to a problem.
Linear time would mean that the processing time is a linear function of the data processed, so a slightly larger problem would only take slightly longer to compute. Quadratic time would be worse for larger problems, since the larger the amount of data, the greater the proportional amount of time.
As the order of these runtimes increase, the harder it is for a computer to quickly search for the solution to that problem. You should note that this doesn't necessarily mean the problem is even difficult to solve; just that the matter of searching for the solution is hard.
The complexity class NP is conjectured to be outside of polynomial time, meaning that an NP-hard problem should not be searchable by any polynomial time algorithm. If you could show that this is possible, you'd prove that P=NP.

>> No.6134409

>>6134401
it means there exists an algorithm that solves the problem and which takes at most Mx^n steps, where n and M are fixed constants and x is the size of the input.

so, as the size of the input grows, the time it takes to compute a solution grows. but, it grows like a polynomial. which is slower growth than, say, the exponential function e^x.

>> No.6134414

>>6134405
So it's not a question of whether or not a problem can be computed, but rather a question of if you can brute-force it in a finite time period?

>> No.6134415

>>6134414
Yeah, it's actually possible to solve small NP-hard problems using computers- it's just that NP-hard problems become nigh insurmountable the larger they get.

>> No.6135930

>>6133919
>that Newton inspires me

>> No.6135951

>>6134059
Yes, without question.
Unless you're 40+, then you probably get a plaque like Wiles.

>> No.6135958

>>6134148
Terry Tao isn't a computer scientist and is more equipped than all of /sci/ combined to determine the relative difficulty of these problems.

>> No.6135968

>>6134415

Let me see if I get this straight. I recall a thread long ago about what was "harder to solve": Math or Chess.

I argued that Chess was harder because it is against time, hence the total amount of possibilities vs time to analyze ratio makes it harder to solve.

Am I getting it right? I may need to lengthen my thoughts...

>> No.6135973

>>6133919
NP=
having the solution to a problem that you don't know exist...
Seems bretty hard

>> No.6135992

>>6135968
Yes, sort of.
Consider this problem: decide if a number is even. It takes the same time for any input - you just look to the last digit. Now consider some problem of finding a Hamiltonian circuit on a graph (http://en.wikipedia.org/wiki/Hamiltonian_path)) this problem gets a lot harder as the number of vertices grows. in other words, a larger input makes the problem much harder.
Problems in P don't get much harder as the input gets bigger (like deciding if an integer is even, which doesn't get harder at all), and problems in NP get a lot harder as the input grows, like the problem of finding a Hamiltonian path/cycle.
Here are a list of problems: http://en.wikipedia.org/wiki/Category:Computational_problems
Those under P get slightly harder as the input grows, and those under NP get much harder as the input grows.

>> No.6136005

>>6133919
Definitely P vs NP. It seems intuitively wrong but goddamn assburgers mathfags need formal proofs.

>> No.6136032

>>6133919
>1.1 P versus NP

Problem with this is that we have no fucking clue how to even approach it.

I don't think we'll ever solve it. We simply don't possess calculus necessary to solve a problem like that.

>> No.6136117

>>6135968
No.

Math is undecidable (infinitely more undecidable than the halting problem or any other that comes up in CS)
Chess is EXTIME-complete

Math requires the all powerful insight of a god to perform. Chess just needs exponential time.

>> No.6136127

>>6133919
>P versus NP
This, since we can't actually prove it, and proving that we can't is impossible as well.