# All Questions

25 views

### Space Complexity For Flood Fill

time complexity of this function is O(n) .. Is space complexity similar? ...
19 views

### On approx-preserving P- and A-reducibilities

Let $X$ and $Y$ be two NPO problems. Let $(f,g)$ be a reduction between $X$ and $Y$, in particular, assume that $(f,g)$ is both P-reduction and A-reduction, i.e., there exist two poly-time ...
14 views

### Is the question about closed reduction using token-passing nets still open?

The question about possible implementation of closed reduction using token-passing nets is asked on page 17 in Token-passing Nets for Functional Languages by Jose Bacelar Almeida, Jorge Sousa Pinto, ...
48 views

### Optimization Problem on a Directed Graph

I have the following graph optimization problem. In a directed graph $G$, each node $i$ is endowed with a real value $v_i$ (input) that encodes the minimum "activation threshold" of that node. For ...
39 views

### Complexity of Best known algorigthms for Hamiltonian Cycle?

I think Isaw somewhere that the best known algorigthms for the generaal Hamiltonian cycle problem are O (2^(n/2)) Is this right? What is the best so far Thanks
13 views

### Equivalence of weighted Minkowski sums

Given $n$ polytopes $P_1, \cdots, P_n$, each $P_i$ is given as the V-representation, i.e., a set of $m$ points as its set of vertices. Furthermore, consider a variant of the Minkowski sum (somehow ...
15 views

### Hidden subgroup problem and public key exchange

Which problems relevant to public key exchange can be considered as a hidden subgroup problem? Conversely which hidden subgroup problems are relevant to public key exchange? (We know that for some ...
42 views

### Is Logic Done on Superpositional Bit Values Useful?

Let's say I have a way to represent $N$ bits such that those bits are in a superposition of the $2^N$ possible states those bits can have and that I can do XOR and AND on those superpositional bits to ...
40 views

### Computer Scientist Questions! [on hold]

my name is Dawid, I'am a 5th year student in Colaiste an Chraoibhin in Fermoy Co.Cork. I am interested in being a computer scientist later on in life and I would like to ask you a couple of questions ...
55 views

### Alternatives to Diffie Hellman

Assume that Discrete logarithms can be solved in linear time over any group (hence factorization is also trivial by a result of Eric Bach), is there any other candidate public key exchange problem ...
64 views

### Does it matter who beings communication in $IP(f(x))$?

Consider $IP(f(x))$, in other words, the class of languages that admit a private coin protocol $(P, V)$ running in $f(x)$ rounds (often in terms of the size of $x$), satisfying standard constraints. ...
115 views

### Fastest Turing Machine

Recently I have been reading about Kolmogorov Complexity. As such I started thinking about the "fastest turing machine". In particular I am not interested in finding such a machine, I am only ...
57 views

### Squared Hellinger distance between Binomial(n,p) and Binomial(n+1,p)

I came across a claim in a paper Trace reconstruction revisited (in Lemma 11), which is basically that the squared Hellinger distance between Binomial$(n,p)$ and Binomial$(n+1,p)$ grows as $O(1/n)$. ...
60 views

### Why can't we have superlinear bounds on Boolean circuit size for an explicit function?

I am interested about the minimal size (number of gates) of a family of circuits (with negation) over a complete Boolean basis (with fanin 2) that computes some explicit Boolean function. (In other ...
56 views

### Functional oracles

In the traditional oracle Turing machine, the oracle is specified as a decision problem. Roughly speaking, one puts a string in the oracle tape, and asks whether it is true or false. I am wondering ...
15 views

### Is that “every infinite history H of x, an infinite number of method calls are completed” mean, that x object is lock-free?

Is the following statement equivalent that object x is lock-free? For every infinite history H of x, an infinite number of method calls are completed. I believe the answer is yes, but I can't proof ...
25 views

### Constructing a regular expression from a NFA [on hold]

I am trying to find the regular expression from the following NFA's and would like some feedback on whether or not I am correct and why! I used the following algorithm to come up with my answers, ...
37 views

### Proof software for Primitive Recursive Arithmetic

Primitive Recursive Arithmetic is a critical foundational system in mathematics at large, and all the more so in areas studying constructive reasoning and/or computability such as Theoretical Computer ...
50 views

### Looking for reference proving polynomial-time bounds for A* search under specific conditions

In the textbook "Artificial Intelligence - A Modern Approach" (Russel, Norvig), it mentions that a sufficient criteria for the A* search algorithm to complete in polynomial time is for the heuristic ...
23 views

### Counting words of length $n$ in an inherently ambiguous CFG?

There is a polynomial-time algorithm for computing the number of words of length $n$ in an unambiguous CFG $G = (V, \Sigma, R, S)$ (via a dynamic programming approach). However, for ambiguous CFGs, ...
75 views

### What does “Computers cannot solve a problem for which there is no solution outside the computer” means? [on hold]

I have been on a research team which is investigation the case "Computers cannot solve a problem for which there is no solution outside the computer". I have surfed the internet for more than enough ...
97 views

### Graph isomorphism problem with invertible adjacency matrices

This question is supplementary to the question asked here. One of the answers give a class of graphs for which the adjacency matrices are invertible which is defined as follows. Given a ...
89 views

### Generating uniform integers in a range from a random generator with another range

Let $p$ and $q$ be two positive integers. I have an oracle that can generate a uniform integer in $\{1, \ldots, p\}$, the integers thus produced being independent across oracle calls. My goal is to ...
111 views

### Directed multigraphs as minimal automata

Given a regular language $L$ on alphabet $A$, its minimal deterministic automaton can be seen as a directed connected multigraph with constant out-degree $|A|$ and a marked initial state (by ...