Coming soon - Get a detailed view of why an account is flagged as spam!
view details

This post has been de-listed

It is no longer included in search results and normal feeds (front page, hot posts, subreddit posts, etc). It remains visible only via the author's post history.

0
Has someone found a polynomial time heuristic for an NP-hard problem, but no one has been able to find a counterexample?
Post Body

Let's say hypothetically, someone's discovered a heuristic to solve Sudoku puzzles of n x n sizes, as the size gets larger and larger the brute force search for a counterexample is not practical.

Unfortunately, it seems there is no easy way to generate a puzzle where the heuristic fails.

What if this heuristic was actually an unproven correct algorithm that solves every instance of n x n puzzles in polynomial time?

Even if the general consensus is that we don't think it works, we have searched for a very long time for a counterexample but haven't found one. Perhaps no counterexample exists.

Is it possible, that general consensus has prevented research into further exploration into heuristics?

Are there any known heuristics that haven't been formally proven?

What does that say about the limitations of modern mathematics, if a heuristic hasn't been disproven?

Author
Account Strength
100%
Account Age
5 years
Verified Email
Yes
Verified Flair
No
Total Karma
24,555
Link Karma
18,260
Comment Karma
5,746
Profile updated: 1 day ago

Subreddit

Post Details

We try to extract some basic information from the post title. This is not always successful or accurate, please use your best judgement and compare these values to the post title and body for confirmation.
Posted
8 months ago