0
votes
0answers
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 ...
-3
votes
0answers
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 ...
-4
votes
0answers
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 ...
1
vote
0answers
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 ...
-2
votes
0answers
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 ...
-2
votes
0answers
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 ...
0
votes
1answer
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. ...
4
votes
1answer
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 ...
6
votes
2answers
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 ...
-1
votes
1answer
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 ...
3
votes
0answers
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 ...
-5
votes
0answers
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.
-4
votes
0answers
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 ...
1
vote
0answers
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 ...
-3
votes
0answers
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 ...
-2
votes
0answers
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 ...
-3
votes
0answers
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 ...
6
votes
1answer
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 ...
0
votes
1answer
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 ...
4
votes
0answers
102 views

Local Graph Isomorphism to construct Global Graph Isomorphism

Does there exist a Graph Isomorphism Algorithm that uses Local Isomorphism to construct a Global Isomorphism? For example, two graphs are given, say, $H, G$. it is asked to determine whether $G\simeq ...
5
votes
1answer
106 views

Classes of graphs with superconstant treewidth

There are several interesting classes of graphs with bounded treewidth. For instance, trees (treewidth 1), series parallel graphs (treewidth 2), outerplanar graphs (treewidth 2), $k$-outerplanar ...
-5
votes
0answers
61 views

Can a problem with exponentially many solutions be solved in polynomial time? [on hold]

I'm trying to make sense of $P$ versus $NP$ and I have a couple questions that I believe will clarify things. Mainly, can a problem with exponentially many solutions be solved in polynomial time? That ...
3
votes
3answers
85 views

Random grid point in a d-dimensional ball

I would like to know if there is any standard algorithm to generate a random grid point inside a d-dimensional ball with a given radius r. Thanks Bin Fu
1
vote
0answers
42 views

Matching of points in two discrete linear sequences with potentially missing points

This is a question that I've been thinking about in my research lately. I've gone down the route of a few linear-optimization techniques, but nothing particularly spectacular has come up. Anyway, the ...
-1
votes
1answer
82 views

Does Huffman coding always produce shorter codes than the Shannon code?

Let $X\in\{1,2,\ldots,m\}$ be a discrete random variable with $X\sim p$. Let $C$ be a code for $X$ with $l_i$ being the length $i$-th codeword and let $L(C)$ be the expected length of the code. In ...
7
votes
0answers
59 views

Partitioning a rectangle without harming inner rectangles

$C$ is an axis-parallel rectangle. $D_1,\dots,D_n$ are pairwise-interior-disjoint axis-parallel rectangles such that $D_1\cup\dots\cup D_n \subsetneq C$, like this: A rectangle-preserving ...
0
votes
1answer
53 views

`f_equal` isn't doing anything

I'm trying to do the following thing: take a set (here, nat, for the sake of simplicity), define a subset of "valid" values (here, even numbers), and then prove ...
-1
votes
0answers
35 views

Complexity class of “Construct a new boolean formula for deciding all 2^n QBFs of a boolean formula”

A large monotone boolean formula Q can be constructed for deciding all $2^N$ QBFs of an original boolean formula P, by treating the quantification portion of P as a boolean assignment in Q. When P is ...
2
votes
1answer
111 views

Circuity complexity: monotone circuit of Majority function

As showed in the paper "Monotone Circuits for the Majority Function", is possible to construct a monotone boolean circuit for the majority function on n variables with size O(n^3) and depth 5.3 ...
4
votes
1answer
55 views

Growth rate of primitive recursive functions

Pardon me for asking a question whose answer is surely well-known, but is beyond my expertise: Q. Is the growth rate of each primitive recursive function $f(n)$ bounded by some exponential ...
1
vote
1answer
107 views

Graph class with easy chromatic number, but NP-hard coloring

Is there a graph class for which the chromatic number can be computed in polynomial time, but finding an actual $k$-coloring with $k=\chi(G)$ is NP-hard? Without any further restriction the answer ...
-1
votes
0answers
16 views

Indirect Left recursion

I'm solving (indirect Left Recursion) for these production rules . S is the starting symbol. S -> Aa / a eq1 A -> Sb / b. eq2 Now I can do this in two ...
-2
votes
0answers
73 views

NP problems for which there exists “greedy” algorithms [closed]

I suspect that a problem that can be solved to optimality by incremental improvements (ie a "greedy algorithm") can be said to be in NP if a polynomial time algorithm for computing the incremental ...
5
votes
0answers
136 views

Is there a special name for the following type of graphs?

Weighted graphs such that if $x$ and $y$ are nodes in the graph, and $p$ and $p'$ are two paths in the graph between $x$ and $y$, then the weight of $p$ equals the weight of $p'$.
7
votes
1answer
92 views

A word anticorrespondence problem

A problem instance is a finite list of 4-tuples $(\alpha_1, u_1, v_1, \beta_1), ..., (\alpha_N, u_N, v_N, \beta_N)$, where $\alpha_i, \beta_i \in X$ come from a finite set, and each $u_i,v_i \in A^*$ ...
5
votes
2answers
132 views

The relationship between degree of vertex and size of dominating set

I was wondering is there any relationship between degree of vertex and size of dominating set. For example, if I know the number of vertices is $n$, and I could know each vertex in the graph has ...
1
vote
1answer
41 views

Is unbounded quantum fanout operation experimentally feasible?

It is known that the "unbounded quantum fanout operation" is very powerful: (See, for example, Hoyer et al. : http://theoryofcomputing.org/articles/v001a005/v001a005.pdf). In particular, it is known ...
4
votes
1answer
41 views

Is there a “lambda cube” for interaction nets?

The lambda calculus is an untyped language that is often extended with logical frameworks such as the vertices of the λ-cube. Is there something similar to it, but for interaction nets? What about ...
-4
votes
1answer
65 views

NP-completeness of one generalized subset sum problem (target sum belongs to interval)

I need to prove that decision problem: for a given set of positive integers $a_1, ..., a_n$, does it exist a subset that sums up to a value within interval $[\frac{1}{2}\sum a_i; \frac{1}{2}\sum ...
-2
votes
0answers
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!!!
0
votes
0answers
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 ...
-1
votes
1answer
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 ...
5
votes
1answer
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 ...
4
votes
0answers
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 ...
1
vote
0answers
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' ...
-3
votes
0answers
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 ...
1
vote
1answer
67 views

Normal form for deterministic (sub)sequential transducers with letter-by-letter outputs

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 ...
5
votes
1answer
72 views

A special case of the boolean multivariate quadratic polynomial problem

It's well known that in the general case, the boolean MQ problem: given $(f_1, \ldots, f_n) \in \mathbb{F}_2[x_1, \ldots, x_m]$ with $\deg(f_i) = 2$, can we find a solution $\vec{y}: f_i(\vec{y}) = ...
5
votes
1answer
133 views

Is it possible to find a non-cut vertex in O(|V|) time?

Let $G = (V, E)$ be an undirected connected graph, which is represented by an adjacency list. A vertex is called a cut vertex if removing this vertex with its incident edges from $G$ makes the graph ...
1
vote
0answers
85 views

Minimizing a monotone submodular function under a cardinality constraint

I would like to know what the status of the following question is: Given query access to a non-decreasing, non-negative submodular function $f\colon 2^{[n]} \to \mathbb{R}$ and a parameter $0 ...

15 30 50 per page