# All Questions

12,315 questions
Filter by
Sorted by
Tagged with
13 views

### Difference between ''Optimization'' and ''Evaluation'' problem?

I have a question, regarding a definition that I found in the book ''Introduction to Linear Optimization'' (from ''Dimitris Bertsimas'' and ''John N. Tsitsiklis'' (1997), Page 517), regarding the ...
24 views

### Reference for "A Turing machine cannot be equipped with an oracle for itself"

Starting with a basic Turing machine, successive applications of the Turing jump produce successively more powerful machines, that can be indexed by any ordinal. A tempting error for students, and one ...
• 757
66 views

### Halting problem proofs that do not utilise self-reference or diagonalization

Are there any proofs of the Halting problem that do not involve any self-reference, and diagonalization (or any diagonal argument) whatsoever? All the duplicate questions I have come across end up ...
20 views

• 113
92 views

### Is there an established name for this kind of upper bound?

Assume for some algorithmic problem it holds that, for each $\epsilon>0$, there is some algorithm that needs space at most $O(n^\epsilon)$. Is there an established name for this kind of bound? I'd ...
• 1,417
1 vote
32 views

### Maximum degree of the Sum of Squares certificate of a non-negative degree d polynomial on the boolean hypercube

Let $f: \{0, 1\}^n \rightarrow \mathbb R$ be a polynomial on the boolean hypercube. If $f$ is non-negative $(f \geq 0)$ i.e. $f(x) \geq 0, \forall x \in \{0, 1\}^n$ then $f$ always has a degree $2n$ ...
• 111
48 views

### Efficiently checking that points lie on a polynomial

Say I am given $n$ points $y_1, …, y_n$ in a finite field, and want to check whether they lie on a polynomial $f$ of degree $t < n-1$ with $f(i)=y_i$. The obvious way to do this is to interpolate a ...
• 1,162
68 views

### $NP \subseteq PSPACE$ proof clarification on enumeration of all solutions [closed]

I was asked to prove that NP is a subset of PSPACE using certificates (no reductions). It's incredibly obvious if you can iterate through every possible solutions of the problem in polynomial space, ...
• 109
448 views

### Is classical lambda calculus grammar an LL(k) one?

I am playing with a lambda calculus and faced a question I find hard to reason about. On the screenshot you may find the lambda calculus grammar. Is it an instance of the ...
• 214
75 views

### Why do some problems seem to admit a richer family of algorithms than others?

Let's take integer multiplication and comparison sorting as examples. Despite being roughly comparable in terms of computational complexity, if we look at the set of algorithms which solve each ...
• 503
1 vote
97 views

### Communication complexity of equality on graphs

I came upon a nice observation in communication complexity, and I was wondering if it was already known. Consider the following variant of the equality problem: There is a fixed graph $G$ that is ...
• 5,290
52 views

116 views

### Consistent Sampling a Random Walk

Assume there's a random walk $S_k = X_1 + \dots + X_k$ where $X_i \in \{1, -1\}$ are uniformly iid. I want Alice and Bob to share a function $S(k) = S_k$. A straightforward approach would be to let ...
• 898
89 views

71 views

### Circuit computing Longest Increasing Sub-sequence (LIS)

Taking inspiration from sorting networks, I was wondering if another prominent algorithm can be implemented in the same fashion: finding the longest increasing sub-sequence (LIS), Input is given as ...
• 679
4k views

### Theoretical Computer Science vs other Sciences?

So I‘m in my third semester studying Computer Science at a German university, so I‘ve only scratched the surface of Theoretical Computer Science, namely Logic, Formal Languages, Automata Theory, ...
• 117
69 views

### Cycle packing with degree condition

Given a directed graph where each vertex has the same in-degree as out-degree, I would like to find the maximum number of edge-disjoint cycles. Is this NP-hard? Without the degree condition, the ...
• 113
57 views

### Equivalent Characterizations of Semilinear Sets

Coming from an automata theory background, the semilinear sets seem like an ideal candidate for having lots of equivalent characterizations. I am already familiar with a few well known ones: Sets ...
• 209
29 views

### Tape reduction, tape compression and time compression

In our lecture we have the following relationships: I have problems to understand these abstract classes. First of all, our Turingmachines are defined as $1$ input tape and $k$ working tapes. DSPACE(...
1 vote
216 views

### Turing Machines and Logic

It is well known that Monadic Second Order Logic (over words) and finite automata can express the same set of languages. Is there a logic over words (perhaps a nth order logic) such that it and turing ...
• 123
374 views

### Is it NP-hard to find an order on a set of strings so that the concatenation is a given string?

Consider the following decision problem over a fixed alphabet $\Sigma$: Input: strings $s_1, \ldots, s_n$ of $\Sigma^*$ and a target string $t \in \Sigma^*$ Output: does there exist a permutation \$\...
• 8,223