# All Questions

8 views

### Two extremely naive questions about the Kronecker problem from Geometric Complexity Theory

I was reading the GCT IV paper (http://arxiv.org/pdf/cs/0703110v4.pdf) and while the representation theory is clear enough (by which I do not mean to say 'easy'!) the relation to complexity theory as ...
20 views

### No-instance of uncolored graph isomorphism

I am trying to learn the polynomial time reduction from the colored graph isomorphism to the regular graph isomorphism, I posted a question. It was answered in a vague way. Later, I found another ...
17 views

### proof by induction automato

Consider the following automaton, $A$. Prove using the method of induction that every word/string $w\in L(A)$ contains an odd number(length) of $1$'s. Show that there are words/strings with odd ...
62 views

### New proofs from “The Book”

The book "Proofs from The Book", referencing Erdős' notion of God's book, which contains the most beautiful proofs, was published in 1998. Are there any new proofs that should be considered for ...
14 views

### Converse of “implicant” in boolean function?

Implicant is a product term P when it is true then other boolean function F is true. Now suppose the converse: if a product term P is false then F is false. What is the name for this "converse ...
21 views

### master method/recurrence

I am given a recurrence T(n) = 3T(n/2) + n^2 lg(n) Is it possible to use master theorem to find a T(n) = theta(f(n))? There is polylogarithmic function as f(n) but as I understand there is a limited ...
36 views

### Lowerbound for the minimum distance between points in a “nice” triangulation

Suppose we have a unit square $S$ that contains $n$ points. Assume we always have a point at each of the four corners. No we triangulate $S$ by adding non-intersecting segments between the points. ...
82 views

### Is length uniform AC0 computable?

Consider the following problem: Input: A binary string $w$. Output: $|w|$ as a binary number. Is it possible to compute this in $\mathsf{DLogTime}$-uniform $\mathsf{AC}^0$ (or equivalently in ...
174 views

### Complexity of counting matchings in a bipartite graph

I might be missing something obvious but I can't find references about the complexity of counting matchings (not perfect matchings) in bipartite graphs. Here is the formal problem: Input: a ...
50 views

### On the difference between propositional proof system and polynomially-bounded proof system

For the definition of a propositional proof system we have: An abstract proof system is a polynomial time function f whose range is equal to the set of tautologies. If τ is a tautology, then an ...
53 views

### Quantum GCD circuit: On reversibility and clearing ancillae

Originally posted on PHYS, however, obviously it has more to do with CS I am currently trying to implement a circuit for computing the greatest common divisor in the Quantum Computing Language. In my ...
25 views

### Automata Theory. Regular Expressions [on hold]

Simplify: 1) a c | b c | a c c* | b c c c* | b | a 2) c | b ( b | E ) b* c | b b* b b c The E is épsilon.
31 views

### How to prove that TQBF ̸∈ SPACE(n^1/3 ) [on hold]

TQBF is PSPACE-complete. P stands for polynomial. I understand that (from Wikipedia): In mathematics, a polynomial is an expression consisting of variables (or indeterminates) and coefficients, that ...
108 views

### Oracle for NP complete problems

What if we had an oracle for solving all NP problems which has exactly one solution in polynomial time. The oracle fails if the NP problem has more than 1 solution. The question is can we use this ...
40 views

### 2DPDA Acceptance

Let $u$ be the given word on alphabet $\Sigma$. $L1(u)=\{x: x$ has been obtained from $u$ by inserting exactly one letter from $\Sigma$ at one position in $u \}$ $L2(u)=\{x: x$ has been obtained ...
33 views

### Theory of Computation: Multi headed Turing Machine Simulation [on hold]

I am a undergraduate student taking a theoretical computer science course. I have the pleasure of learning firsthand from a genius, but am unfortunately having difficulty keeping up with him. I am ...
44 views

### Border between P vs NP in traveling salesman or other NP problems [on hold]

When considering a problem like the traveling salesman. What specifics must be satisfied for the problem to be NP-hard. For example if there are only 2, 3, 4... cities, when does it become NP-Hard? I ...
70 views

### Precise definition of syntatic categories / syntatic domains in abstract syntax

I have read the introductory parts of a couple of books on programming language semantics (Gordon, Winskel, Nielson & Nielson, Allison, Stump, Schmidt), and while I do understand what they mean by ...
47 views

### How to specify and verify Horn clauses (logic programming programs)? Semantics of Horn clauses

There are lot of applications of Horn clauses (notable examples include use of rules in cognitive architectures and knowledge bases, as well as use of rules in business rules programs). Are there ...
102 views

46 views

### Hamiltonian path in 3-connected graph [closed]

I have tried to find answer for my question, but I did not get result. I have a question:"Does there exist HAMILTONIAN PATH in 3-connected graph?" Thank you very much!!!
50 views

### On NP-hardness of list decoding of RS codes

Given an $[n,k,n-k+1]_q$ Reed Solomon code we know that . Unique decoding upto half minimum distance can be done in polynomial time. . List decoding upto $n-\sqrt{nk}$ can be done in polynomial ...
45 views

### Packing $n$ objects into $m$ bins whose size is variable

Assume we have $n$ fixed size objects with sizes $O_1$ to $O_n$. Also, assume we have $m$ bins with size $a \times B_1$ to $a \times B_m$ in which $a$ is a real number and $a\ge1$. We want to put ...
123 views

### Binary Search with Errors

Suppose I give you $n$ labelled coins $C_1, \cdots, C_n$ of unknown bias. I promise you that the coins have been sorted by bias (i.e. $\forall i~~\mathbb{P}[C_i=1]\leq\mathbb{P}[C_{i+1}=1]$) and at ...
107 views

### Finding median in a changing array

Consider the problem of needing to support an $n$ integers array structure with two operations: Set(k,v) - set the $k$'th integer to value $v$ (i.e. $A[k]=v$). Median() - return the median value of ...
75 views

### NP Intermediate problems over Reals

While studying ${\bf NP}$ complete problems we have from Ladners' theorem - if ${\bf P}$ $\neq$ ${\bf NP}$-there are ${\bf NP}$ problems not in the class ${\bf P}$ nor ${\bf NP}$-complete. Ladners' ...
7 views

### Clustering algorithm for heterogeneous object [closed]

Could anyone point out to the algorithm or literature that talk about clustering of complementary objects?  I am interested in algorithm that make cluster of objects that have complementary wind ...
For a project I'm working on, it would seem useful to have a normal form for deterministic (sub)sequential transducers in which the set of states, $Q$, is partitioned into states, $r \in Q_R$, that ...