Problem description: NP problem solutions can be verified in Polynomial time.
Problem description: NP problem solutions can be verified in Polynomial time. Every problem in NP can be reduced to a NP complete problem. These in turn can be reduced to a logic gate circuit to represent a Boolean Truth Table ( SAT or Boolean satisfiability problem?). Assume a Boolean Truth table, with number of columns as (N) and rows as (2^N). Now search for one specific random row in this table (Solved Rubik's cube Config). Every-other row computes to one while only this row computes to zero (Exact Global minima). So do NP complete problems occurring in nature have a hidden pattern or is Brute force the only resort in the worst case scenario, as it is currently? A) To prove P = NP, find a polynomial time algorithm to solve 1) If a given graph has a Hamiltonian Circuit of path length less than length 'k' (Decision problem) or to solve 2) The Traveling salesman Problem (Shortest path). B) To prove P =!NP, prove that no such algorithm can ever be invented :) __________________________________________________ I've shared the chat I've had with an AI LLM, as a precursor to a "ICALP LICS FSCD 2024 - Award Talks" (see youtube video description for link). Why is there no easy way to understand Professor Ryan Williams work : https://www.wired.com/2015/10/major-advance-reveals-limits-c... Given that this is such an important problem, there should be more easy to understand, advanced education material around this! Some additional resources : https://courses.csail.mit.edu/6.890/fall14/lectures/
Posted by npvsp on Aug 21, 2024, 3:37 PM
Tags
Related issues
- I mean that's the problem though.
- I've always believed the opposite: get conditionals deep in your code so that the higher level control flow is regular.
- The biggest problem with AI isn't being able to do things.
- I am a 3D printing maker type nerd (I make my own tools for other creative tasks, rather than as their own outcomes) and I saw an incredi...
- Of course not, those are clearly scams.
- Claude makes more detailed plans that seem better if you just skim them, but when analyzed, has a lot of errors, usually.
Raise real-world problems, find people facing the same issue, and discuss solutions.8,000 issues0 comments
hackernews (EdTech)
I mean that's the problem though.
I've always believed the opposite: get conditionals deep in your code so that the higher level control flow is regular.
The biggest problem with AI isn't being able to do things.
I am a 3D printing maker type nerd (I make my own tools for other creative tasks, rather than as their own outcomes) and I saw an incredi...
Of course not, those are clearly scams.
Claude makes more detailed plans that seem better if you just skim them, but when analyzed, has a lot of errors, usually.
Effectively everyone is building the same tools with zero quantitative benchmarks or evidence behind the why / ideas … this entire s...
> creating and operating a small company in Germany is a nightmare To be fair, I think the problem operating in Germany is its federated...
Problem description: NP problem solutions can be verified in Polynomial time.
Problem description: NP problem solutions can be verified in Polynomial time. Every problem in NP can be reduced to a NP complete problem. These in turn can be reduced to a logic gate circuit to represent a Boolean Truth Table ( SAT or Boolean satisfiability problem?). Assume a Boolean Truth table, with number of columns as (N) and rows as (2^N). Now search for one specific random row in this table (Solved Rubik's cube Config). Every-other row computes to one while only this row computes to zero (Exact Global minima). So do NP complete problems occurring in nature have a hidden pattern or is Brute force the only resort in the worst case scenario, as it is currently? A) To prove P = NP, find a polynomial time algorithm to solve 1) If a given graph has a Hamiltonian Circuit of path length less than length 'k' (Decision problem) or to solve 2) The Traveling salesman Problem (Shortest path). B) To prove P =!NP, prove that no such algorithm can ever be invented :) __________________________________________________ I've shared the chat I've had with an AI LLM, as a precursor to a "ICALP LICS FSCD 2024 - Award Talks" (see youtube video description for link). Why is there no easy way to understand Professor Ryan Williams work : https://www.wired.com/2015/10/major-advance-reveals-limits-c... Given that this is such an important problem, there should be more easy to understand, advanced education material around this! Some additional resources : https://courses.csail.mit.edu/6.890/fall14/lectures/
Comments (0)
No comments yet. Start the discussion.