All Questions

Filter by
Sorted by
Tagged with
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$...
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 ...
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,...
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 ...
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, \...
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 ...
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)↑....
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 ...
-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 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 ...
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 ...
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 ...
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 ...
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 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 ...
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 ...
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) = ...
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 $$\...
-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 ...

15 30 50 per page
1
2 3 4 5
241