15

Here is an example, where one can produce a solution in polynomial time, but evaluating a given solution is NP-hard. Input: Positive integers $n,k$ (in unary encoding), with $k\leq n$. Task: Maximize the number of edges in an $n$-vertex graph under the constraint that its maximum clique size is at most $k$. Solution: It is known from extremal graph ...


14

Concerning Question 1, there have mainly been two lines of work to find tractable restrictions of SAT. The first one that you are already familiar with is to restrict the types of the clauses that you are allowed to use. For example, in 2-SAT, you are only allowed to use size two clauses. In Horn-SAT, you only allow Horn clauses etc. The tractable ...


9

Let $L$ be an EXPTIME-complete language, and let $r \in (0,1)$ be the corresponding real. Clearly $r$ is computable. The number $r$ cannot be algebraic since the $n$th bit of an algebraic number can be computed in time $n^{O(1)}$ (Datta and Pratap). Since the $n$th bit of any number computable by a real-time Turing machine can be computed in time $O(n)$, $r$ ...


7

There is a general theory here, which was introduced into CS by Robin Milner, which Lamport did not go into. A state machine is generally given as a triple $(Q \in \mathrm{Set}, q \in Q, f \in I \times Q \to \mathcal{P}(O \times Q))$, consisting of a state set $Q$, an initial state $q$, and a transition relation $f$. Now, suppose we have two automata $(Q,...


7

Superpolynomial time complexity cannot be in P. While this appears easy to believe, it is actually a false belief. Formally, we may think that if $f(n)$ is a superpolynomial function, then ${\mathsf {DTIME}}(f(n)) \not\subseteq {\mathsf P}$. Surprisingly, this is wrong. In fact there exists a superpolynomial function $f(n)$ with $${\mathsf P} = {\mathsf {...


5

"When a problem is algorithmically undecidable, it means that it has a definite provable answer (yes or no) on all instances, but no unique algorithm is capable to reach this answer uniformly on all instances." It was a revelation for me to discover that any undecidable problem has particular instances that are independent of ZFC. Otherwise, ...


4

Not quite what you're looking for, but the iterated mod problem is a P-complete number-theoretic decision problem.


3

You can trivially consider NEXP-complete problems and they satisfy all 3 conditions that you're looking for. And by the Time Hierarchy Theorem, NP is strictly in NEXP.


3

In paper [1], there is a problem with the property that finding an optimal element takes polynomial time despite that computing the objective function values is NP-hard (it means that evaluating the quality of a given candidate solution is NP-hard as well). [1] T.C.E.Cheng, Y.Shafransky, C.T.Ng. An alternative approach for proving the NP-hardness of ...


2

Suppose we have a binary symmetric channel: $x_1 \rightarrow y_1$ with probability $1-\epsilon$ and $y_2$ with probability $\epsilon$, $x_2 \rightarrow y_2$ with probability $1-\epsilon$ and $y_1$ with probability $\epsilon$. Now add a third input $x_3$ that goes to $y_1$ and $y_2$ with probability $\frac{1}{2}$ each. Then the optimal input ...


1

How about the following counter-example? $m=2$, $n=4$. $A=\{a_1,a_2\}$, $B=\{b_1,b_2\}$, $C=\{c_1,c_2\}$. $T=\{(a_1,b_1,c_1), (a_1,b_2,c_2), (a_2,b_1,c_2), (a_2,b_2,c_1)\}$. With the partition $A\cup B\cup C = \{a_1,b_1\}\cup\{a_2,b_2\}\cup\{c_1\}\cup\{c_2\}$.


1

You can use the example for an undirected edge with unit capacities, but replace each undirected edge from A to B with a set of directed edges that look like this. Each edge has a unit capacity. And if you have $x$ units of flow from A to B and $y$ units of flow from B to A, you can route it as long as $x+y \leq 1$. This is the gadget referred to in ...


1

A paper of mine with Gupta and Kumar titled On a bidirected relaxation for the MULTIWAY CUT problem was also based on running experiments. In fact we were trying to prove the converse of what we ended up proving. Vazirani, in the first edition of his book on approximation algorithms, suggested that the bidirected relaxation was at least as good as the ...


1

My recent paper with Karthik Chandrasekharan titled Hypergraph $k$-cut in deterministic polynomial time was based on extensive computational experiments. We explored different conjectures and submodular functions and found counter examples to several different approaches. The truth of the main structural theorem was suggested by experiments and we then ...


1

Some recent results in state complexity were found with the help of systematic brute-force search for worst-case examples. This is doable because there are not too many deterministic finite automata with a small number of states, for example if we concentrate on binary or ternary alphabets. Also, in many cases there are families of worst-case examples for $1,...


1

In 2018, Aubrey de Grey found a 1581-vertex, non-4-colourable unit-distance graph. This gives a lower bound of five for the famous Hadwiger-Nelson problem. He used a computer to verify that the graph indeed has chromatic number at least five. Gil Kalai's blogpost covers some facts and further developments. An article in the quanta magazine reports that he ...


Only top voted, non community-wiki answers of a minimum length are eligible