26

I think that there is a fundamental underlying difficulty with the question you are asking here (and that you asked in your related question about incomprehensible languages). Roughly speaking, it seems you're seeking a language $L$ such that $L\in P$ but ZFC doesn't know that $L\in P$. To understand the difficulties with your question, I think you must ...


7

Not exactly what you're looking for, but Dinur and Safra, in their celebrated paper on the hardness of vertex cover, prove that the following promise problem is NP-hard for every fixed $r,\epsilon > 0$ (using the PCP theorem and Raz's parallel repetition theorem). Instance: A graph $G$ whose vertex set is composed of $m$ sets $V_1,\ldots,V_m$ of size $r$,...


5

The usual terms I know from the theory of posets and lattices are downset and upset (or upper set). Also as the empty set is a subset of every set, I think your first condition is vacuous as long as the system is not empty. Same for the first condition in the second definition. If a downset is closed under joins (in your case set unions), it is called an ...


3

The complexity of enumerating maximal independent sets in graphs is the same as in bipartite graphs, so bipartiteness does not bring anything new. You have an algorithm (with exponential space) in $O(|C|\cdot n^2)$, but no polynomial space algorithm that acheives this time complexity is known. The following paper http://www.sciencedirect.com/science/...


3

See Sherali and Smith's 2006 paper A polyhedral study of the generalized vertex packing problem. They consider a subset of vertices whose induced subgraph has at most $k$ edges. There are many other generalizations of independent set and clique, based on degree, density, number of edges, distance, diameter, etc. Independent sets go by other names (e.g., ...


2

You can do it with the isolation lemma. Here are the important details (admittedly hastily written): We'll imagine picking a hash function from $H$ as follows: first, pick $w_1^0,\ldots,w_n^0,w_1^1,\ldots,w_n^1$ uniformly and independently from integer weights in $[1,4n]$. Then pick a threshold $T$ in $[1,4n^2]$ also uniformly and independently at random. ...


2

On (1): The case of stable sets in graphs may clarify the situation (a stable set of a graph is a set of pairwise non-adjacent vertices). For each graph $G$, let $\mathcal{S}(G)$ be the set of stable sets of $G$. The graphs $G$ for which the non-trivial facets of $P(V(G),\mathcal{S}(G))$ (i.e the stable polytope) are all rank-facets are called rank-perfect ...


2

Apparently not. "Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence", by Mathias Bæk Tejs Knudsen and Morten Stöckel shows "a $k$-independent family of functions that imply [heaviest loaded bin] size $\Omega(n^{1/k})$".


1

Definition 1: Let $x_n := 2 + \sum_{i=0}^n [1/2^i \mbox{ if $i$ encodes a proof that $\bf{ZF}$ is inconsistent, and 0 otherwise}]$. Clearly, we can build a Turing machine which, given $n$, will compute $x_n$. Also the $x_n$ converge to $x := 2 + \sum_{i=0}^\infty [1/2^i \mbox{ if $i$ encodes a proof that $\bf{ZF}$ is inconsistent, and 0 otherwise}]$. So $x$ ...


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