Have any NP-hard problems in math ever been solved?
>>8070834
What do you mean solved? Lots of applied computer science requires us to find solutions to instances of NP-hard problems.
I'm working on some graph theory weirdness that with some more development might give rise to a general solution method for NP-hard problems, but I'm not sure if it's feasible or not yet because that's not the main focus of what I'm doing.
>>8070844
By solved I mean transofmred into a problem where a solution can be found to any instance of the problem.
For example, for the traveling salesman problem, that would be finding the lest cost path every time given the inputs we specify (such as the distance between cities, the conncections between cities, etc.)..
I'm taking the traveling salesman problem as an example because it's NP-hard (and NP-complete).
>>8070834
for all variable assignments:
if formula with assignments == true:
return true
end if
end for
return false
>>8070851
Most NP-hard problems admit a tree structure (each branch of the tree corresponds to a non-deterministic choice made by the Turing machine). NP-hard problems can usually be solved by enumerating solutions and searching them. There are complications in that (e.g. will the enumeration actually get to the solution, if there is one? will it terminate when there is no solution?) but they're mostly plumbing. Not sure if there's a general method of doing this.
>>8070864
I should say all NP-complete problems (an NP-hard problem could be harder than NP and not solvable by the same methods).
>>8070864
Thanks for your response.
But I'm talking about mathematical problems that can be considered as NP-hard, or at least NP-complete, such as the traveling salesman problem in graph theory.
Has this type of problem ever been solved?
That is, has this type of problem ever had an algorithm found that would solve it? Not just check whether the solution is right, but actually find the solution based on the problem only?
>>8070892
If what you mean by solve is "find a solution in linear time" then no.
>>8070851
>By solved I mean transofmred into a problem where a solution can be found to any instance of the problem.
All NP problems can be solved, in principle. For non-small problems, it just takes a tremendous amount of time and resources to do so. NP problems are not magic. They can all be solved by brute forcing, as per the definition of the set of NP problems.
>>8070959
Have any small NP-complete (math) problems been actually solved? If so, what are some examples?
By solved I mean a solution was obtained with any time complexity, be it linear, polynomial, exponential, etc.
>>8070966
>Have any small NP-complete (math) problems been actually solved? If so, what are some examples?
Again, all of them have been solved.
I think you need to review this post:
>>8070958
My paraphrase: Has anyone found a P-time solution to any NP-complete problem? No. But that's not the question you asked. You just asked "has any NP problem been solved" aka "has anyone found a solution algorithm for any NP problem", and the answer is "yes, there is a trivial solution algorithm for all NP problems, which runs in exponential time".
>>8070966
The travelling salesman problem is solvable. You just list every possible route, compute the length of each route, and take the shortest.
NP-complete doesn't mean unsolvable, it means unsolvable in polynomial time amongst other things.
>>8070973
>it means unsolvable in polynomial time amongst other things.
Almost certainly true, but note that this is not the proper definition.
In English, the proper definition of NP problems is: All problems where a potential solution can be verified right / wrong in P-time.
IIRC, the definition of NP-complete is the set of all problems so that if there exists a P-time solution to one of the NP-complete problems, then there exists a P-time solution for all NP problems.
We don't have proof, but currently everyone (more or less) is convinced that NP is not P.
>>8070986
Hmm... that's ambiguous. Let me try again.
NP: The set of all problems where a particular possible answer can be verified right/wrong in P-time.
NP-complete: The set of all problems in NP so that if there exists a P-time solution-finder to one NP-complete problem, then there exists a P-time solution-finder to all NP-complete problems.
My previous post was ambiguous on "answer" vs "solution finder".
>>8070991
If there is a P time solution to NPC, there is a P time for all NP
>>8070996
Yep.
>>8070969
>Again, all of them have been solved.
What are some examples? The traveling salesman problem is NP-complete, yet no solution has been found so far.
>>8071002
Thanks, I get what was being said now.
Though his post assumes that P=/=NP.
NP-complete means that a problem is both NP and NP-hard, not that it's unsolvable in polynomial time (unless P=/=NP).
>>8071009
P = NP remains an open academic question in academic mathematics and academic computer science.
In practice, everyone knows that they're not the same, and that there is no P-time solution-finder to any NP-complete problem.
>>8071001
Here's how you solve it:
You generate all circular paths that visit each city exactly once.
Then you compare all paths and find the shortest one.
The problem is that the amount of paths you have to compare grows really (exponentially) fast if you add more cities.
Brainlet here. I have a somewhat related question, and don't want to create a new thread.
What do you call the set of all possible algorithms that can be used solve the same problem?
>>8071546
Dunno if that has a particular formal name.
>>8070834
Every one has been solved, if it was unsolved it wouldn't be NP-hard.
>>8072004
Fuck off, trip fag.
>>8070834
Find the shortest path that starts at A, passes through B, C and D, and returns to A.
Congratulations, you've solved an NP-hard problem.
>>8070991
Pretty sure your NP definition is false, any NP problem could be his own NP-complete class by your definition.
>>8070966
You obviously have no idea what an NP problem is.
>>8070851
Not sure if you are tolling but NP-hard is more of an abstract notion that refers to anything that is NP-Complete or harder in the sense that it takes longer than it takes longer than Poly-time to verify.
For example, travelling salesman is NP-complete and NP-complete since it can be verified in polynomial time. But chess is a game where it is even harder than NP. For instance, I can never gove you a sequence of moves that are guaranteed to win everytime since for each move you can make a counter move that could destroy my startegy. But for something like travelling salesman, once you found the path. That path will always be the right answer no matter how many times you travel it.
Do you see the pattern?
i believed john von neumann solved this problem right before he died but the solution was lost when his documents were moved to storage.
Hey guys I recently solved The P Versus NP Problem. I have posted the proof document on facebook. My name is Victor Isai Mazariegos. The fb profile is easily locatable - my most recent post is about The Collatz Conjecture. You can e-mail me at [email protected].
>mfw this thread is what /sci/ has become
