2
$\begingroup$

I was thinking in the following approach for solving a problem that is believe to be a NP-hard problems today in polynomial time, assuming the following:

  • There exists a believed-today NP-hard problem called $X$, where its whole input space can be divided into a finite set of groups such that there exists a corresponding "single-threaded" polynomial-time algorithm for each group (that only runs polynomically for the inputs corresponding to its designated group, without any complexity guarantees regarding inputs for other groups).

Since we don't neccesarily have a criteria to know, polynomically, to which group a certain input belongs to, a possible approach to solve such problem $X$ polynomically is to run all algorithms in parallel and wait for the first that finishes, aborting the execution of everyone else.

Since we have at least one polynomial-time algorithm for every possible input of $X$ (because of the conditions given above), and we are executing all algorithms at once, such problem will be solved in polynomial time for every input, and so every believed-today NP-hard problem can be solved polynomically previous transformation to an instance of $X$.

Is there any research in this direction?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ What does "believed-today NP-hard" mean? If a problem is shown to be NP-hard today, then this a fact with a mathematical proof. It will still be NP-hard tomorrow, even if someone proves P=NP or its negation. Perhaps it would also be a good idea to check what "NP-hard" means. There are multiple reasonable definitions of NP-hardness, but I don't think any of them have an expiration date. $\endgroup$
    – Discrete lizard ♦
    Oct 11, 2020 at 15:51
  • $\begingroup$ I meant that a polynomial time algorithm hasn't been found so far. $\endgroup$
    – ABu
    Oct 11, 2020 at 15:51
  • 2
    $\begingroup$ That is not what NP-hard means, see this introduction for example. In particular, while it is unknown whether there is a polynomial time algorithm for factoring, it has not been shown to be NP-hard, and is not expected to be NP-hard. $\endgroup$
    – Discrete lizard ♦
    Oct 11, 2020 at 15:57

2 Answers 2

Reset to default
3
$\begingroup$

$X$ doesn't exist (unless $P = NP$ in general) because your description is self-contradictory. You claim it is NP-hard, yet its input domain can be split in a finite number of disjoint poly-time solvable problems. This makes it $P$.

The idea of executing these algorithms in parallel adds nothing. Even on a single machine you can run N programs 'simultaneously' by distributing computational time in a round-robin fashion, leading to an overhead factor of N to any single program. Set N to be equal to your number of algorithms (which was, by your description, a finite constant), and you end up with a poly-time algorithm.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I have added the notion of "believed-today NP-hard" in the description of the problem. Does it remove the contradiction? $\endgroup$
    – ABu
    Oct 11, 2020 at 15:44
  • $\begingroup$ @Peregring-lk No, because as I just shown, your "finite disjoint poly-time" property implies P. You'd be claiming "believed-today P = NP". $\endgroup$
    – orlp
    Oct 11, 2020 at 15:45
  • $\begingroup$ Maybe I don't have the knowledge to properly describe the intention of the question. I was thinking in categorizing the input domain (not the actual input of a specific instance), like when we categorize simple graphs according if they are planar, bipartite, stars, complete, and such. For example, the maximum clique problem can be solved in polynomial time if its input is a planar graph. I also removed the "non-exponential amount of groups" because it makes no sense. $\endgroup$
    – ABu
    Oct 11, 2020 at 15:50
  • $\begingroup$ @Peregring-lk As long as this categorization is finite and complete (that is, no parts of the input space are left out), and each part has a poly-time algorithm solving it, then the original problem is poly-time, if the original problem is in NP. $\endgroup$
    – orlp
    Oct 11, 2020 at 15:51
  • 1
    $\begingroup$ @Peregring-lk I don't know. $\endgroup$
    – orlp
    Oct 11, 2020 at 16:00
1
$\begingroup$

No, I'm not aware of any research in this direction, probably because it is not very promising. This does not seem to me like a promising approach to solve NP-hard problems efficiently, or other hard problems efficiently. The hard part would be how you would find that decomposition; I don't know of any reason to think that's particularly easier than solving the entire problem.

If the problem had the structure you described, with only polynomially many groups, then the problem could be solved in polynomial time. Anything you can do in parallel, you can do with a single thread by interleaving execution. After all, many CPUs are single-threaded, yet can execute many processes (seemingly in parallel, though actually interleaved).

You talk about "believed to be NP-hard", but most of the NP-hard problems we encountered are not just "believed" to be NP-hard; they are known to be NP-hard, and we can prove it.

My answer does not change appreciably if you replace "believed to be NP-hard" with "believed to be hard".

Improve this answer
$\endgroup$
3
  • $\begingroup$ Yeah I'm aware that with "believed to be NP-hard" I take a very bad choice. I should have said something like "believed to be untractable in deterministic computers" or something like that, but there's too many references in comments to the current wording as to changing it now. $\endgroup$
    – ABu
    Oct 11, 2020 at 22:18
  • $\begingroup$ And the "interesting" aspect of my question is to divide the input space $S$ in a set of subspaces $S_i$ so you can write an algorithm $A_i$ for each $S_i$ that runs polynomically if the input happens to be in $S_i$ and expotentially otherwise. The usual research on "algorithms" are based on single strategies (maybe with some checking for dealing with specific cases), but I'm interesting in which attempts has been made in creating taxonomies of inputs, for example a complete (idelly disjoint) categorization of graphs that could be useful to write independent algorithms targeting each category. $\endgroup$
    – ABu
    Oct 11, 2020 at 22:27
  • $\begingroup$ @Peregring-lk, OK. I've edited my answer. I think what I should have said is that it does not seem like a promising approach. I'd guess there might not be any research because it doesn't help. $\endgroup$
    – D.W. ♦
    Oct 11, 2020 at 23:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.