1
$\begingroup$

Sample-Question

Intro

I'm seeking clarity after many failed attempts to understand a few sentences that I read from a Wikipedia page. So I'm asking here on Computer-science for better understanding.

Misconception From Wikipedia

Unless P=NP any poly-time algorithm must asymptotically be wrong on more than polynomially many of the exponentially many inputs of a certain size.Wikipedia

Question

Why and how is that easy instances of NP-complete problems that are solved in poly-time do or don't have any consequence on the P vs NP problem?

What are the mis-conceptions if I had an algorithm that solves non-finite Easy instances of any n-size of the 3-coloring problem in O(n) time?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

This looks like a good, valid question if you expand what to do with your Easy instances.
If you have some method that works fast for subset of instances and works only for them, say cycle graphs and want to infer anything about P = NP, there is a mistake, but this is a reasonable question.

"Suggestions" is probably list of links with similar questions detected by system, on the right side of page while preparing post before submission.

$\endgroup$
1
  • $\begingroup$ Yes, the project is complete but now I want to show it without Sudoku easy instances for other problems that share the same permutation problem. I don't want a P = NP crank proof thats not my intentions. $\endgroup$
    – Travis Wells
    Jun 7, 2019 at 13:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .