Most Popular
1500 questions
15
votes
3 answers
Progress on generalized star-height problem?
The (generalized) star height of a language is the minimum nesting of Kleene stars required to represent the language by an extended regular expression. Recall that an extended regular expression over a finite alphabet $A$ satisfies the…
Patrick Papadopulos
- 251
- 1
- 5
15
votes
1 answer
Hitting set of pairwise intersecting families
A hitting set of a family $\mathcal{S} = \{S_1, \dots, S_n\}$ is a subset $H$ of $\bigcup_{i=1}^{n} S_i$ such that $H \cap S_i \ne \emptyset$ for $1 \le i \le n$.
The problem to find a minimum hitting set of a given family is NP-hard in…
Yota Otachi
- 1,731
- 15
- 24
15
votes
5 answers
References for Modular Decomposition
What are good papers/books to better understand the power of Modular Decomposition and its properties?
I'm particularly interested in algorithmic aspects of Modular Decomposition. I have heard that it is possible to find a Modular Decomposition of a…
Vinicius dos Santos
- 1,868
- 12
- 21
15
votes
2 answers
The existence of planar distance preserver?
Let G be an n-node undirected graph, and let T be a node subset of V(G) called terminals. A distance preserver of (G,T) is a graph H satisfying the property
$$d_H(u,v) = d_G(u,v)$$
for all nodes u, v in T. (Note that H is NOT necessarily a subgraph…
Hsien-Chih Chang 張顯之
- 7,638
- 4
- 44
- 83
15
votes
1 answer
Looking for papers and articles on the Tarskian Möglichkeit
Some background: Łukasiewicz many-valued logics were intended as modal logics, and Łukasiewicz gave an extensional definition of the modal operator:
$\Diamond A =_{def} \neg A \to A$ (which he attributes to Tarski).
This gives a weird modal logic,…
Rob
- 815
- 8
- 19
15
votes
1 answer
Fixed point theorems for constructive metric spaces?
Banach's fixed point theorem says that if we have a nonempty complete metric space $A$, then any uniformly contractive function $f : A \to A$ it has a unique fixed point $\mu(f)$. However, the proof of this theorem requires the axiom of choice -- we…
Neel Krishnaswami
- 32,528
- 1
- 100
- 165
15
votes
0 answers
Intersecting Complexity Classes with Advice
In on hiding information from an oracle, the authors (Abadi, Feigenbaum, and Kilian) wrote:
$(\mathsf{NP/poly} \cap \mathsf{co\text-NP}{/poly})$ ... is not known to be equal to $(\mathsf{NP} ∩ \mathsf{co\text-NP}){/poly}$.
They…
Sadeq Dousti
- 16,479
- 9
- 69
- 152
15
votes
5 answers
Looking for papers and articles on modal substructural logics
I am looking for papers and articles on modal substructural logics-- not on the semantics of linear logic modalities, but on substructural logics augmented with standard modal operators, e.g. substructural K (something like MALL with box operator,…
Rob
- 815
- 8
- 19
15
votes
2 answers
Law of the Excluded Middle in complexity theory
A recent blog post by Lance Fortnow discusses non-constructive proofs, where "non-constructive" here means that the law of the excluded middle is used in a substantive way. That is, one takes some proposition $P$ whose truth is unknown, and splits…
Timothy Chow
- 7,550
- 35
- 43
15
votes
1 answer
Average-case tautologies/contradictions, beyond the random k-CNF model
It is well known that random $ k $-CNF formulas over $ n $ variables with $ cn $ clauses are unsatisfiable (i.e. they are contradictions) with high probability, for sufficiently large constant $ c $. Thus, random $ k $-CNF formulas (for $ c $ large…
Iddo Tzameret
- 1,899
- 1
- 19
- 27
15
votes
3 answers
Bob's Sale (reordering of pairs with constraints to minimize sum of products)
I've asked this question on Stack Overflow a while ago: Problem: Bob's sale. Someone suggested posting the question here as well.
Someone has already asked a question related to this problem here - Minimum weight subforest of given cardinality - but…
Vladimir Panteleev
- 263
- 1
- 6
15
votes
5 answers
Hardness of FPT problems
Vertex Cover can be easily reduced to Independent Set and vice versa.
However, in the context of parameterized complexity, Independent set is harder than Vertex Cover. A kernel with $2k$ vertices exists for Vertex Cover, but Independent Set is W1…
Nikhil
- 664
- 7
- 15
15
votes
4 answers
Counting the number of vertex covers: when is it hard?
Consider the #P-complete problem of counting the number of vertex covers of a given graph $G = (V, E)$.
I'd like to know if there is any result showing how the hardness of such problem varies with some parameter of $G$ (for example, $d =…
Giorgio Camerani
- 6,842
- 1
- 34
- 64
15
votes
1 answer
Data structures in programming language with linear types
Assume we are dealing with a programming language that has support for linear types (terms of linear type can be used at most once, so to say). This allows for treating some computational effects (such as mutation, even changing the type of the…
user3722
15
votes
1 answer
Computability and continuity
Say $L_1$ and $L_2$ are computable languages. Let $f$ be a function $L_1 \rightarrow L_2$. Let $C$ be the statement, "if $l \subseteq L_2$ and $l$ is a computable language, the preimage $f^{-1}(l)$ is a computable language." Does $C$ imply that…
causative
- 255
- 1
- 5