Suppose that $P \neq NP$, and $P = BPP$.
Assume one is given a decision language $L \in NPC$, and she has only polynomial time turing machines. Additionally, she can't use randomness (not sure that's relevant since I assumed $P= BPP$).
How can she compare between two algorithms $A_1, A_2$? Clearly, $A_1$ and $A_2$ cannot be correct for every input (they must run in polynomial time). Does it make sense to define the better algorithm as the one which answers correctly on more inputs? (And two algorithms will be equal when they answer correctly on the same number of instances).

Are there known methods to do so?

  • $\begingroup$ Heuristics for NP-hard problems are often analyzed experimentally by running them on a large sets of instances, and by looking at the solution quality. Often it's also the case that heuristic A is better on certain type of input (say dense graphs) than heuristic B, but it is vice versa on some other type of input. $\endgroup$
    – Juho
    Nov 1, 2018 at 11:36
  • $\begingroup$ I am aware of this experimental method. However, is there a theoretical framework for this case? $\endgroup$
    – R. Davis
    Nov 1, 2018 at 11:42
  • $\begingroup$ At least in terms of runtime, yes. One increasingly popular approach is performing a parameterized analysis. That is, instead of measuring runtime as a function of only input size, you also consider some other parameter, like solution size or some structural measure. Most often this is done for hard problems, but there is recent work like this on aspects of heuristics and generally problems in P. $\endgroup$
    – Juho
    Nov 1, 2018 at 12:04
  • $\begingroup$ Thanks. I guess these approaches assume the algorithm is always correct (and then you only care about the resources it uses). What I am trying to understand here is the opposite: you are given the amount of resources you are allowed to use, and among all these algorithms, I am trying to define an order relation $\endgroup$
    – R. Davis
    Nov 1, 2018 at 12:09
  • $\begingroup$ One would hope that any "interesting" algorithm would give the correct answer for infinitely many inputs. So, at that point, you're not going to be able to compare simply by cardinality. $\endgroup$ Nov 1, 2018 at 14:36


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.