# All Questions

12,974 questions
Filter by
Sorted by
Tagged with
70 views

### Reductions That Acts on Witnesses

We say that a language $X$ is polynomial time reducible to $Y$, intuitively, if given an algorithm for solving $Y$, there's an algorithm for solving $X$. I know this can be formalized using Karp ...
80 views

### What are some practical applications of inductive-inductive and inductive-recursive types?

Since this question got not many answers Im hoping asking again could convey that this has some importance. Anyway so in undergraduate education, I was working on research to implement dependent-...
115 views

### How well can shortest common supersequence over small alphabet size be approximated?

Given a list $L$ of sequences of the first $n+1$ natural numbers, how well can we approximate the shortest common supersequence of all sequences in $L$? The paper here shows that if $n$ is not ...
• 228
83 views

### Polynomial time algorihtms for two variants of the decision version of longest walk problem

I want to know if the following variants of the longest path problem over directed graphs have polynomial time algorithm. As I understand it, the longest path problem doesn't allow repetition of edges....
• 1,049
105 views

### Constructing complex languages without "recursion"

I'm curious of the ways we can construct provably complex languages. In particular, most constructions (i.e., the one used for proving the Time hierarchy theorem) seem to rely on encodings of Turing ...
• 117
83 views

### Complexity of chess with 50-move rule

It is known that evaluating who wins in $n \times n$ chess positions is EXP-complete (and thus unconditionally not in P), and this effect is due to the game having rich possibilities for exponentially ...
104 views

### By Gödel numbering, is the set of computable(partially) transcendental numbers an immune set, productive set? [duplicate]

Every Turing Machine computing(output) real number is encoded as a natural number, namely, admissible numbering. Then what is the set of computable (partially) transcendental numbers? Is it an immune ...
• 1,079
53 views

### Shortest sequence that contains a given list of sequences as subsequences

Given an alphabet with $n$ characters, and a list $L$ of sequences can we approximately find the shortest sequence that contains all sequences of $L$ as subsequences? Very similar to the question ...
• 228
54 views

• 10.8k
46 views

### Unbounded Knapsack: Does Increasing capacity increase optimal value?

Our decision problem is as follows: given weights $\mathbf{w}$, values $\mathbf{v}$, and capacities $C_1$ and $C_2$, where $C_1 < C_2$, does the optimal value of unbounded knapsack with the above ...
1 vote
63 views

### Not possible to write deterministic CFG for balanced parenthesis?

I know that it's possible to build an LL(1) parser for the Dyck language, i.e. a balanced string of parentheses, so the Dyck language is a deterministic context-free language. But what's an example of ...
• 163
151 views

• 120
1 vote
178 views

### Is (Restricted) Bigraph Isomorphism Weaker than Graph Isomorphism?

I am investigating a paper from Dominik Grezlak and and Uwe Aßmann: “A Canonical String Encoding for Pure Bigraphs.” On page 2, they define the notion of a bigraph, which is roughly a forest and ...
117 views

### Given $a_i$ -$r$ paths $P_i$ in a planar graph construct a tree spanning $a_i$ such that each root to leaf path intersects few $P_i$

Suppose I am given distinct nodes $a_1,a_2,.., a_l, r$ and edge disjoint $a_i$-$r$ paths $P_i$ for each $i$ in a planar graph $G$. I wish to construct a tree $T$ connecting $a_1,a_2,.., a_l, r$ ...
• 228
1 vote
54 views

### Is there a sharp phase change on error rate near the error correction threshold?

My rough intuition is that if we want to efficiently compute using noisy gates, the probability of success will exhibit threshold behavior as we cross the error correction threshold. Here is an ...
• 3,263
1k views

### List of nice non-context-free languages

I am trying to separate classes of formal languages from each other. One of these classes is the class of context-free languages. To this end, it would be handy to have a list of languages which are ...
• 233
60 views

### What is Shutt abstractiveness?

In software development, there is a pre-formal notion of abstraction. Several attempts have been made to formalize it. In particular, what is Shutt abstraction, or Shutt abstractiveness, and how does ...
• 271
75 views

### What is the actual difference between uniformity conditions for NC¹

I want to know what the actual difference between the uniformity conditions for NC¹ is. I know that for $k\geq 2$ $NC^k$ the uniformity conditions are equivalent, but for NC¹ they are not. I am ...
• 31
133 views

### Is there a full abstraction result for an untyped lambda calculus?

Famously, the denotational semantics of PCF in Scott domains is not fully abstract. But by adding the parallel or construct to PCF, a fully abstract semantics can be obtained. Is there an analogous ...
• 225
394 views

• 111
1 vote
44 views

### Constructing a DFA with $n$ states for which $L*$ needs $n$ equivalence queries

I'm working on constructing deterministic finite automata (DFAs) with a specific learning complexity when using the L* algorithm developed by Dana Angluin. My goal is to create a DFA of size ( n ) ...
155 views

### The most complex language? [closed]

I'm interested in understanding the complexity of languages. If I wanted to construct a language that is very difficult to decide, how would I go about this? Is it known whether we can artificially ...
• 117
5k views

### Data structure whose name starts with the letter “N”?

I’m working on an “ABC” poster of data structures, with one data structure per letter of the alphabet. (It’s intended as decor for a child’s room.) I teach an advanced data structures course and it ...
101 views

### Original formulation of Spira's Lemma

I'm currently reading the book "Proof Complexity" by Jan Krajíček (2019), where Spira's Lemma is mentioned: Let $T$ be a finite $k$-ary tree and $|T| > 1$. Then there is a node $a \in T$ ...
• 181
1 vote
104 views

### Why does the Time Hierarchy Theorem fail relative to promise problems?

Define Program Evaluation (PE) to be the promise problem of determining whether a program (written in a Turing-complete language) returns True or False. The promise is that the program will return ...
• 528
21 views

### Detection of intersection between two $d$-dimensional convex polytopes with at most $N$ facets

I am looking for a reference on the current state-of-the-art algorithm(s) for detecting intersection between two $d$-dimensional convex polytopes, with time complexity depending on their number of ...
1 vote
88 views

I was reading old lecture from a CS course at Cornel and I have some doubts about the following at 2.4 It defines how to transform domains between each other via a Galois Insertion, more formally: ...
• 11
281 views

### Is GCT still active?

Is Mulmuley's geometric complexity theory program still active? I tried to look it up online, and I haven't seen anything from the last couple of years.
• 14k
57 views

### How to estimate slope of a feature in image?

I am working on analyzing data obtained from acoustic sensors. During analysis of acoustic data, I got frequency-wavenumber spectrum of acoustic data as shown below. I am looking for a technique that ...
60 views

### Is greedy minimax permutation rejecting sorting optimal?

I sketch an impractical, theoretical comparison sort for sorting array $a$ of size $n$. Initialize a list of all $n!$ permutations of size $n$. For each possible pair of indices $i, j$, count how ...
• 885
56 views

• 2,252
208 views

### Research masters programs in theoretical computer science (with a focus on complexity theory)

I am in my 2nd year of my Computer Science degree. I am deeply interested in Complexity Theory, and I plan to pursue a career in this field I am from South Asia, and research here is not up to par, ...
76 views

### References for algorithms to compute approximating polytopes for arbitrary convex sets

There is a vast theoretical literature on approximating convex, compact bodies in $d$-dimensional space $\Bbb R^d$ by convex polytopes. One of the main results in this area is that under some mild ...
Has anyone thought about what constraints a monad should satisfy in order for its arrows to be able to be "applicativized". That is, for what monads $M$ is it the case that there is an ...