We show improved NPNP-hardness of approximating Ordering-Constraint Satisfaction Problems (OCSPs). For the two most well-studied OCSPs, Maximum Acyclic Subgraph and Maximum Betweenness, we prove NPNP-hard approximation factors of 14/15+ε14/15+ε and 1/2+ε1/2+ε. When it is hard to approximate an OCSP by a constant better than taking a uniformly-at-random ordering, then the OCSP is said to be approximation resistant. We show that the Maximum Non-Betweenness Problem is approximation resistant and that there are width-mm approximation-resistant OCSPs accepting only a fraction 1/(m/2)! of assignments. These results provide the first examples of approximation-resistant OCSPs subject only to P≠NP.

We give the first examples of non-trivially positively-useless predicates subject only to P != NP. In particular, for every constraint function Q : {-1,1}^4 -> R, we construct Contraint-Satisfaction-Problem (CSP) instances without negations which have value at least 1-eps when evaluted for the arity-four odd-parity predicate, yet it is NP-hard to find a solution with value significantly better than a random biased assignment when evaluated for Q. More generally, we show that all parities except one are positively useless. Although we are not able to exhibit a single protocol producing hard instances when evaluated for every Q, we show that two protocols do the trick. The first protocol is the classical one used by Håstad with a twist. We extend the protocol to multilayered Label Cover and employ a particular distribution over layers in order to limit moments of table biases. The second protocol is a modification of Chan's multi-question protocol where queried tuples of Label Cover vertices are randomized in such a way that the tables can be seen as being independently sampled from a common distribution and in effect having identical expected biases. We believe that our techniques may prove useful in further analyzing the approximability of CSPs without negations.

The Canadian traveler problem (CTP) is the problem of traversing a given graph, where some of the edges may be blocked-a state which is revealed only upon reaching an incident vertex. Originally stated by Papadimitriou and Yannakakis (1991) [1], the adversarial version of the CTP was shown to be PSPACE-complete, with the stochastic version shown to be in PSPACE and #P-hard. We show that the stochastic CTP is also PSPACE-complete: initially proving PSPACE-hardness for the dependent version of the stochastic CTP, and proceeding with gadgets that allow us to extend the proof to the independent case. Since for disjoint-path graphs, the CTP can be solved in polynomial time, we examine the complexity of the more general remote-sensing CTP, and show that it is NP-hard even for disjoint-path graphs.

We show improved NP-hardness of approximating Ordering Constraint Satisfaction Problems (OCSPs). For the two most well-studied OCSPs, Maximum Acyclic Subgraph and Maximum Betweenness, we prove inapproximability of 14/15 + ε and 1/2 + ε. An OCSP is said to be approximation resistant if it is hard to approximate better than taking a uniformly random ordering. We prove that the Maximum Non- Betweenness Problem is approximation resistant and that there are width-m approximation-resistant OCSPs accepting only a fraction 1/(m/2)! of assignments. These results provide the first examples of approximation-resistant OCSPs subject only to P ≠ NP. Our reductions from Label Cover differ from previous works in two ways. First, we establish a somewhat general bucketing lemma permitting us to reduce the analysis of ordering predicates to that of classical predicates. Second, instead of "folding", which is not available for ordering predicates, we employ permuted instantiations of the predicates to limit the value of poorly correlated strategies.

Håstad established that any predicate P01^m  containing parity of width at least three is approximation resistant for almost satisfiable instances. However, in comparison to for example the approximation hardness of Max-3SAT, the result only holds for almost satisfiable instances. This limitation was addressed by O'Donnell, Wu, and Huang who showed the threshold result that if a predicate strictly contains parity of width at least three, then it is approximation resistant also for satisfiable instances, assuming the d-to-1 Conjecture. We extend modern hardness-of-approximation techniques by Mossel et al. to projection games, eliminating dependencies on the degree of projections via Smooth Label Cover, and prove, subject only to = , the same approximation-resistance result for predicates of width four or greater.

Håstad established that any predicate P ⊆ {0,1} m containing parity of width at least three is approximation resistant for almost satisfiable instances. However, in comparison to for example the approximation hardness of Max-3SAT, the result only holds for almost satisfiable instances. This limitation was mitigated by O'Donnell, Wu, and Huang under the d-to-1 Conjecture. They showed the threshold result that if a predicate contains parity of width at least three, then it is approximation resistant also for satisfiable instances. We extend modern hardness of approximation techniques by Mossel et al. to projection games, eliminating dependencies on the degree of projections via Smooth Label Cover, and prove unconditionally the same approximation resistance result for predicates of width four.