All Questions
12,016
questions
0
votes
0
answers
15
views
Can the witness for an NP-search problem be distinct from the item sought?
Related to NP-search, consider the following problem:
Given a two-to-one function $f(x)$, find $(d,y)$ with $d\ne \bf 0$ such that there exists a pair $(x_1,x_2)$ with $f(x_1)=f(x_2)=y$, and also $d\...
- 852
1
vote
0
answers
12
views
Unclear proof step in Feder and Greene's 1988 paper showing NP-Hardness of approximating k-center problem within a factor of 1.82
I was reading the paper "Optimal Algorithms for Approximate Clustering", Feder and Greene [1988] (https://dl.acm.org/doi/10.1145/62212.62255).
Specifically, I was trying to look at the $1.82$...
- 111
0
votes
1
answer
12
views
What is region construction in timed automata?
I've recently started self-learning timed automata.
There's this theorem in there that a timed automaton can be converted to a DFA using a "region" construction. I've looked up references on ...
- 101
0
votes
0
answers
10
views
Dual of cut of embedded graph disconnects surface
Let $G$ be a graph that embedded on a surface of genus $g$, moreover the embedding is triangulated. Let $C$ be a collection of edges that forms a minimal edge cut for $G$. Let $M^*$ consist of the ...
- 2,267
0
votes
1
answer
63
views
On the proof of $PP = P \iff \#P = FP$ in Arora & Barak (Lemma 17.7)
Introduction
I am currently studying chapter 17 (of the famous textbook by Arora & Barak [1]) on the complexity of counting and got stuck on the proof of Lemma 17.7, which states $\mathrm{PP} = \...
- 171
5
votes
1
answer
120
views
Can you define recursive predicates in 2nd order intuitionistic logic?
This is a purely logical question, but I think it's adjacent enough to CS that it's worth a shot here.
Take 2nd order Heyting Arithmetic, say Heyting Arithmetic with an extra sort of (unary) ...
- 13.3k
4
votes
0
answers
86
views
Languages recognized Counter DFA
I just randomly started fooling around with formal languages, grammars, and machines, and I have an extension to DFAs that I do not know what the class of languages it can recognize is.
I'll give a ...
- 141
2
votes
0
answers
72
views
How to implement the next type inference algorithm?
Here I mean only simple typed Lambda calculus / Combinatory logic.
Notation: Combinatory logic terms: $F, X_i, Y_i$. Term application: $(F*X_1)$. Type variables $x_i,y_i$. Type assignment: $X:x_i$.
...
- 121
0
votes
0
answers
40
views
Polynomial GCD exact complexity in terms of degree and number of variables
https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Proof_that_GCD_exists_for_multivariate_polynomials states multivariate polynomial GCDs may be defined over $\mathbb F_p[x_1,x_2,\dots,...
- 12.5k
-6
votes
2
answers
209
views
Does the Linz Halting Problem proof contain a fatal flaw?
It is the case that the input to the embedded Linz H would never reach its final state and halt when the Linz H is a simulating halt decider. (see below).
computation that halts… the Turing machine ...
- 65
-1
votes
0
answers
24
views
NCness of unique solution fixed dimension integer programming
Consider the promise problem of fixed dimension integer programming with promise being that there is exactly one witness. The problem is in $TFNP$. If the promise problem is in $FNC$ then integer $GCD$...
- 12.5k
0
votes
0
answers
20
views
Quantifying the cost of procedures
Is there any research on quantifying the cost of a procedure, with regard to compiler optimization?
I.e. assigning some kind of cost in terms of CPU time or memory to a procedure, either so the ...
- 111
2
votes
0
answers
35
views
Is there any context-free language that is inherently ambiguous as an indexed language
Indexed languages are defined as being produced by indexed grammar.
Is there any context-free language that is inherently ambiguous as an indexed language? That is, is there a context-free language ...
0
votes
0
answers
26
views
What is the tightest lower bound known for the integrality gap of the Gilmore–Gomory LP for Bin Packing?
I know that it has been conjectured that the Gilmore–Gomory LP for 1-D BP (also known as configuration LP) has
Modified Integer Roundup Property, i.e., Opt ≤ ⌈Opt_f⌉ + 1. However, I could not find the ...
- 11
2
votes
1
answer
93
views
Exposition of categorical models of type theory from type-theoretic perspective
Are there any formalizations or expositions of categorical models from type theoretic point-of-view? What I have in mind to get a better grasp of categorical models of dependent types, treating ...
- 809
1
vote
1
answer
115
views
Computational complexity and general relativity
According to general relativity, the time that a Turing Machine near a massive object spends on computing every step is longer than the time that the Turing Machine far awayfrom a massive object ...
1
vote
0
answers
49
views
Clarification sought re Li & Vitanyi's Proof of Godel Incompleteness in Formal System F
(Cross-posted from Computer Science due to lack of response after 1 week)
From An Introduction to Kolmogorov Complexity and Its Applications, Li & Vitany, 4th Ed. Example 1.1.1.
As you might guess,...
- 111
1
vote
0
answers
51
views
Is there any inherently ambiguous indexed language?
Indexed languages are defined as being produced by indexed grammar.
My question is: gIs there any indexed language without any indexed grammar that can produce every word or sentence of the language ...
2
votes
0
answers
54
views
Efficient algorithm for finding closest point for rotated and scaled $\mathbb{Z}_n$ lattice
Suppose we have a $\mathbb{Z}_n$ lattice generated by the identity matrix $I_n$. Here I would like to consider a rotated and scaled $\mathbb{Z}_n$ lattice $\Lambda$ with the generator matrix $M=I_n*O*...
- 121
1
vote
0
answers
60
views
Generalizing Fano's inequality
Fano's inequality says the following:
Theorem: Let $X$ be a random variable with range $M$. Let $\hat{X} = g(Y)$ be the predicted value of $X$ given some transmitted value $Y$, where $g$ is a ...
- 11
0
votes
1
answer
63
views
Number of stable matchings
In the stable marriage problem, is it possible to find an instance with $2^{n -1}$ stable matchings when $n$ is a power of 2 (or just even)? If yes, how? I know how to build an instance in which $2^{n/...
- 103
-1
votes
0
answers
69
views
Theorems about integrality gap for set cover linear programs
What theorems about the integrality gaps of linear problems of the form
$$ \begin{array}{c}
\textbf{min} \ \ c^t x \\
\sum_{ v \in C} x_v \geq 1 \ \ \forall C \in \mathcal{C} \\
x \geq 0
\end{...
- 215
4
votes
0
answers
80
views
Time Complexity of Pairwise Graph Connectedness
The Setup
Consider the following algorithmic problem which, for now, I will call $\mathsf{2GraphConnector}$.
Input: A natural number $|V|$, and a finite collection $\mathscr{E} = \left\{E_1, E_2, \...
- 41
0
votes
0
answers
60
views
What is the right notion of reduction for 2EXPTIME?
I've recently been working on some temporal logic problems. In particular, a central result in the field is the fact that realizability for LTL is 2EXPTIME-complete. I've only seen the result quoted ...
- 429
0
votes
1
answer
37
views
Complexity and Applications of performing $N$ divisions with "similar" results?
What is the complexity of performing $N$ divisions with "close" results and does it have applications in practice?
It seems that some algorithms to divide a number $x$ by a number $y$ boil ...
- 2,570
-2
votes
0
answers
106
views
Is this theorem correct? [closed]
THEOREM 1: There are numbers k and s and a program A(n,m) satisfying the following conditions.
If A(n,m)↓, then C_n(m)↑.
For all n, C_k(n) = A(n,n) and C_s(n) = C_k(s).
A(k,s)↓ and for all n, A(s,n)↑....
- 1
2
votes
0
answers
86
views
How far is the distance between Mahlo Universe and Mahlo Cardinal?
There seems to be some literature stating that Mahlo Universe[1][2] is the counterpart of Mahlo Cardinal in type theory, but I don't fully understand this point of knowledge.
More explicitly, I would ...
- 21
-1
votes
1
answer
46
views
Flow of value lower bounded by $X$
In a given network, is it possible to find a flow of value that is lower bounded by $X$ in near-linear time, $O((m + n) \text{poly}\log n)$? I do not want to find the exact maximum flow just whether ...
0
votes
0
answers
66
views
Interactive proofs with computation bounded Merlin
Consider usual interactive proofs (Arthur is polynomial-time bounded and can use random bits)
where computation power of Merlin is bounded by polynomial-size circuits.
For example, every unary NP-...
- 1,695
1
vote
2
answers
66
views
Examples of promise search problems that are easier than their non-promise variants?
By promise search problem, I mean a search problem for which the solution is guaranteed to exist (e.g. find a solution to a linear system of equations, knowing that a solution does exist).
Are there ...
- 209
-1
votes
0
answers
47
views
What would be a canonical programming language?
Let's say that we need to choose a programming language to serve as the intermediate representation in the middle of a universal source-to-source compiler. This programming language need to be able to ...
- 99
3
votes
2
answers
215
views
Classes between PH and PSPACE
I am interesting in languages of the following form:
$x \in L \Leftrightarrow Q y_1 Q y_2 \ldots Q y_n P(x, y_1, \ldots y_n, x).$
Here every Q is $\forall$ or $\exists$;
$n$ is the length of $x$, the ...
- 1,695
0
votes
1
answer
51
views
Running time of SAT and other EXPTIME algorithms [closed]
I need to propose an algorithm for a NP-hard problem. I use dynamic programming which leads to a running time $O(2^s\cdot n^2), s\leq n.$ The algorithm aims to finding a path in a graph $G(V, E)$ (in ...
0
votes
0
answers
19
views
k-means (Lloyd's algorithm): How many times can cluster configurations repeat until a new one is observed?
I have a small question regarding the dynamics of Lloyd's algorithm for k-means clustering in $d$-dimensional Euclidian space. In every iteration the algorithm generates a set of $k$ clusters, however,...
0
votes
0
answers
88
views
Faster algorithm for sampling unifromly at random
The goal is to come up the simple data structure for sampling a uniform point from a collection of sets, i.e., given a sub-collection
$\mathcal{B}$, sample a point in $\cup \mathcal{B}$
uniformly at ...
- 115
1
vote
1
answer
139
views
Complexity of "discrete-time" SAT
I'm interested in the complexity of deciding satisfiability of the following family of formulae:
$\exists j. I[j(0)] \land \forall t. S[j(t),j(t+1)]$
where:
$j:\mathbb{N} \to \{0,1\}^n$ has finite ...
- 767
0
votes
0
answers
24
views
How can I show that {a,b}∗ & {a,b,c}∗ are in an equivalence relation using the CBS theorem?
I am perplexed about how can I use the CBS theorem to prove that $\{a,b\}^* \cong \{a,b,c\}^*$. I know that for an injection $h : \{a,b,c\}^* \rightarrow \{a,b\}^*$ we can use two-letter codes for a,...
- 1
1
vote
0
answers
57
views
On completeness of LTL
I am reading the seminal paper "On the temporal analysis of fairness" by Gabbay, Pnueli, Shelah, Stavi, available at
shelah.logic.at/papers/134/
In Section 3, completeness of a set of axioms ...
- 11
1
vote
1
answer
191
views
Is it proved that error rate of quantum computation is bounded by constant rather than a function dependent on time and environment by quantum theory
Anyone has proved the error rate of quantum computation is bounded by (less than) a constant rather than a function dependent on time and environment by quantum theory? For error rate and error ...
- 1,059
2
votes
1
answer
295
views
Is any computational complexity question solved by injury priority method except Post problem?
As we know, there are many questions of Turing Degree closed by injury priority method. Is any computational complexity question solved by injury priority method except Post problem or Turing Degree?
...
- 1,059
1
vote
1
answer
156
views
Defining normalization with respect to judgmental equality instead of reduction
In type theory with a type $\mathbb{N}$ of natural numbers (or some other base type such as booleans) and judgmental equality instead of reductions, canonicity is a meta-theoretical statement claiming ...
- 809
3
votes
0
answers
68
views
Solving MDPs with polytope action spaces
A (finite) Markov Decision Process (MDP) consists of a finite set of states $S$, a finite set of actions $A_s$ which we will allow to depend on the state $s\in S$, an initial state $s_0\in S$ (the ...
- 2,161
0
votes
0
answers
68
views
Resources I can use to understand homology/topology as a software engineer?
My professor gave me a research software project this semester:
Port this library: Risper
to a JVM language - either Kotlin, Scala, or Clojure. Now, I have some papers he gave me, but reading them, I ...
- 317
0
votes
0
answers
53
views
Are there parsers that can parse languages in more expressive grammars than context-free grammars?
The Earley Parser is able to parse all context-free languages. Are there parsers that can parse say languages in context-sensitive grammars? I realize ambiguous grammars are non-deterministic and ...
- 101
4
votes
1
answer
106
views
+50
Natural hard communication problems with both nondeterministic and co-nondeterministic complexity of $\sqrt{n}$?
I'm trying to lower bound the worst-case deterministic communication complexity of some special class of functions on $n$ variables, and I've shown that for every function $f$ in the class: $N^1(f) = ...
- 153
2
votes
0
answers
150
views
On the number of optimal prefix-free binary codes [closed]
Let $T$ be a text of length $L$ containing the symbols $$\mathcal{A}=\{a_1, a_2, \ldots, a_n\},$$ where each symbol appears at least once and no other symbol appears in $T$.
Define the weights $$\...
- 21
-1
votes
0
answers
25
views
How to write a simulation to monte-carlo estimate the "probability that such a random coloring on $G$ is successful"
Let $G$ be an undirected $6 \times 6$ lattice graph. The $36$ vertices of $G$ are each randomly colored with one of $5$ colors with equal probability. Such a coloring is called "successful"...
0
votes
0
answers
21
views
Can the actions of one agent serve as the states of another agent in multiple-agent reinforcement learning (MARL)?
Imagine a piplelined process, where agent $A_1$ processes some information, and after that agent $A_2$ does some further processing based on the initial results of the first agent. The agents work in ...
- 1
0
votes
1
answer
173
views
What Complexity Class is this? Is this already known?
Let's call this the Path Game.
For this example, lets imagine a 16x16 grid:
Some of the squares in this grid are "deadly." If you step on it, you must restart and try to go over again. We ...
- 39
0
votes
0
answers
118
views
Is orthogonal polygon with crossings count NP-complete?
The are several NP-complete problems related to the construction of orthogonal polygons. Rapport showed that it is NP-complete to to decide the existence of orthogonal simple polygon that passes ...
- 20.6k