After more than two years, I have to assume the answer is "no". (Posting this stub answer so the question can be marked as answered.)

I am not as convinced as @Andrew Morgan is that this is "fair standard fare", and would also welcome pointers to a citable reduction. In particular, I do not see how to maintain a linear blowup if $k$ ...

This is an extended comment to complement Ryan's answer, which deals with the thresholds where the number of clauses becomes large enough that the instance is almost surely unsatisfiable. One can also ...

One simple "bad" input that needs to be considered for worst-case analysis of this problem is as follows. Let $c=(\sqrt{17}-1)/2 \approx 1.56$. There are three objects of size $c$, $1$, and $1$. ...

Groz et al. explicitly state that the best known algorithm for general regular expressions (as of 2012) is $O(nm(\log\log n)/(\log n)^{3/2}+n+m)$, due to Bille and Thorup 2009, doi:10.1007/978-3-642-...

A problem that is not known to be either in FP or to be NP-hard is the problem of finding a minimal Steiner tree when the Steiner vertices are promised to fall on two straight line segments ...

To add to Daniel's answer, the precise density of hereditary classes has been extensively investigated in combinatorics. For a class $C$ of structures, the unlabelled slice $C_n$ is the set of ...

As far as I can tell, UniqueSAT is exponentially dense, in the sense that it contains $2^{\Omega(n)}$ instances of size $n$. (This is a stronger requirement than $2^{n^\varepsilon}$ for infinitely ...

Multiparty communication complexity and the Number-on-Forehead model were introduced by Ashok K. Chandra, Merrick L. Furst and Richard J. Lipton in Multi-party Protocols, STOC 1983, doi:10.1145/800061....

There is no Zoo-style reference yet, but a recent automata-theoretic survey of Giovanni Pighizzini has been useful to me, especially the slides from his talk. Giovanni Pighizzini, Investigations on ...

Several long-standing key open problems are in the Kushilevitz and Nisan textbook (see also the list of errata which mentions that Open Problem 8.6 was solved by Dietzfelbinger). Razborov's 2011 ...

SAT, CP, SMT, (much of) ASP all deal with the same set of combinatorial optimisation problems. However, they come at these problems from different angles and with different toolboxes. These ...

Denoting the class of functions computed by branching programs of size $f(n)$ by $\text{BP}(f)$, the best known bound seems to be the trivial $\text{DSPACE}(S(n)) \subseteq \text{BP}(2^{O(S(n))})$. ...

Looks like the best bound known (for multitape Turing machines) is logarithmic. Suppose $\delta\log n$ bits of binary worktape is enough to decide whether any $n$-bit CNF formula is satisfiable, for ...

For me, the starkest illustration of the power of non-uniformity is that a suitably padded version of the Halting Problem is already in P/1. A single bit of advice is then enough to decide this ...

If $p$ is constant, then the size of the maximum clique in the $G(n,p)$ model is almost everywhere a constant multiple of $\log n$, with the constant proportional to $\log (1/p)$. (See Bollobás, p....

You are probably looking for this paper: Víctor Dalmau and Peter Jeavons, Learnability of quantified formulas, TCS 306 485–511, 2003. doi:10.1016/S0304-3975(03)00342-6 In short, the learning ...

You remark that lower bounds on $Pn(f)$ are closely related to all existing lower bound techniques. For Boolean functions this seems to be true, as long as the log-rank conjecture is true. However, $...

Conjunctive query containment over bag semantics In a GoogleFight between two search queries, can one tell if the first query always wins, without looking at the data? This 1993 question from ...

An easy case seems to be where the language $S$ contains only padded instances. When $S$ is obtained from a language $L$ by padding each instance of size $n$ with $2^n-n$ symbols, $f^K_{n}$ can be in ...

Deciding reachability for various kinds of infinite-state systems is sometimes decidable, often not. For some interesting special cases a small enough and efficiently checkable certificate always ...

My favourite example is a classic 1977 result of Ashok Chandra and Philip Merlin. They showed that the query containment problem was decidable for conjunctive queries. The conjunctive query ...

Here is a fairy tale about the Goldilocks structure of NP-intermediate problems. (Warning: this story may be a useful fallacy to generate and test potential hypotheses, but is not meant to be ...

My personal (and biased) take is that asymptotic worst-case analysis is a historical stepping stone to more practically useful kinds of analysis. It therefore seems hard to justify to practitioners. ...

It is worth noting that the problem becomes NP-hard when the restriction is relaxed slightly. With a fixed number of clauses that are also of bounded size, the average number of literals in a clause ...

Regarding your second and third questions, you want to know if there is a name for a partial assignment that is guaranteed not to be a nogood, and which will generate only satisfying assignments when ...

There is a large and still growing body of theory about classes of fixed-template constraint satisfaction problems that have polynomial-time algorithms. Much of this work requires mastery of the Hobby ...

Some graph classes allow polynomial-time algorithms for problems that are NP-hard for the class of all graphs. For instance, for perfect graphs, one can find a largest independent set in polynomial ...

The decidability of conjunctive query containment has been open for over twenty years. Resolving this would be a breakthrough in database theory. Query containment takes as input two queries $Q_1$ ...

A particularly striking example of a phase transition is the maximum degree bound for Exactly-$k$-SAT (X$k$SAT), in which each clause contains exactly $k$ distinct literals. The problem flips from ...