# All Questions

26 views

### Sorting a subset of a sorted set; does it need the merge sorting complexity?

Suppose that we have an algorithm in which we have a sorted list of objects like $L = (x_1, x_2, \ldots, x_n)$ (the indices denote the order of the objects). During the algorithm we have a loop where ...
63 views

### NP-Complete Static Square Puzzles

In order to empirically test some CSP algorithms, I would like to compile a list of NP-Complete static board games. By static, I mean that a solution of the puzzle is simply an assignment of values to ...
55 views

### Expander Graph from Hypergraph

I came up with this problem while thinking about an optimizing compiler. Let $H$ be a hypergraph. From this we construct a graph $G_H$ as follows the vertices are the hyperedges of the hypergraph. ...
58 views

### Direct Proof that the Pigeonhole Principle is Hard for Regular Resolution

It is well known that the pigeonhole principle $PHP_n^{n+1}$ is hard for general resolution. The original proof due to Haken is elegant. One first defines a complexity measure for derived clauses, in ...
48 views

### Is this problem involving shortest paths NP hard?

A graph with positive edges is given along with several vehicles at specific vertices of the graph.One of the vehicles has a package that is required to be transferred to a destination node.The ...
39 views

186 views

### Is algorithmic information theory still evolving?

I am currently looking for a subject for a thesis and encountered the field of algorithmic information theory. The field seems very interesting for me, but it seems everything is the field was done ...
85 views

298 views

### Proof techniques for showing that dependent type checking is decidable

I'm in a situation where I need to show that typechecking is decidable for a dependently-typed calculus I'm working on. So far, I've been able to prove that the system is strongly normalizing, and ...
27 views

### The big question: does P=NP? [migrated]

I figured it was a shame that one of the biggest open questions in theoretical computer science was not listed here as a question. True, nobody has an answer (probably), but still. Some might argue ...
50 views

### Sample complexity for learning Boltzmann Distribution parameters

I am trying to think through the number of samples that I would need to estimate the parameters of a Boltzmann partition function to a desirable precision. Suppose that there are N possible states ...
16 views

### Convert grammer in to Greibach form [closed]

The grammer is $S \rightarrow AA|a$$A \rightarrow SA|ab$The actual question is to find an npda accpeting language generated by this grammer but for that i firstly need to convert it into greibach form....
54 views

### Equivalence relations with DFAs [closed]

I'm taking a theory computation class and we've just learned how to formally define a DFA (the 5-tuplet). I'm having difficulty understanding how to manipulate $δ^∗$ in order to prove the equivalence ...
31 views

### Efficient topological sorting of the cartesian product of DAGs

Let us consider n directed acyclic graphs $(G_i)_{1\leq i \leq n}$ and G their cartesian product (with the induced edges) : G is still a DAG. Let us suppose that each vertex has a value, defined as ...
148 views

### Automated theorem proving PhD

I'm looking for a university where I can do doctoral studies in automated theorem proving / computational algebra. Any ideas? Thank you!
41 views

### Is bounded-error quantum polynomial time (BQP) class can be polynomially solved on machine with discrete ontology?

What is your opinion and thoughts about possible ways to get an answer whether problems that are solvable on quantum computer within polynomial time (BQP) can be solved withing polynomial time on ...
8 views

### Is the problem of determining whether a CFG generates a string in the form 0*1* decidable? [migrated]

Given a grammar G, is it decidable whether G generates any string in the form 0*1*? Why? I think it's undecidable but can't find any undecidable problem to reduce it to.
40 views

61 views

### Color shifting in a bipartite graph

Assume that we have a directed bipartite graph $G = \langle L\dot\cup R, E\rangle$. Where $E$ contains directed edges only from $L$ to $R$, that is, $E\subseteq L\times R$. Assume further that the ...
160 views

### How many different proofs are there of parity is not in AC0?

The theorem that Parity is not in $\mathsf{AC}^0$ is one of the gemstones of complexity theory. I wonder how many different proofs there are of this result? What constitutes "different" is also a part ...
25 views

### Heuristics for exact #3COLORING close to the 3-colorability threshold

What are some fast heuristics for exactly counting 3-colorings of graphs close to or at the 3-colorability threshold? Is there literature on the average-case performance for any of these methods?
213 views

### L/quasipoly vs NL/poly

Savitch's theorem shows that NSPACE($S(n)$) $\subseteq$ SPACE($S(n)^2$), which means that nondeterminism can be replaced by more spaces in this situation. Is it known whether nondeterminism can be ...
28 views

### How should a reduction to the Cardinality Constrained Quadratic Knapsack Problem work?

in Polyhedral Study of the Cardinality Constrained Knapsack Problem the authors prove that the Cardinality Constrained Knapsack Problem is NP-Hard by reducing PARTITION to it. Besides, it's easy to ...
229 views

### Algorithm for identifying unprovable statements

I understand that this may depend on the specific set of axioms, but is there a general way (algorithm) for automatically detecting unprovable statements within a set of axioms? For example: If there ...
92 views

89 views

### Efficient quantum algorithm for CLASSICAL FFT

Is there a known improvement on the current O(n*log(n)) algorithm for CLASSICAL FFT using quantum computation? 'n' is the number of samples. I need to find the amplitude and phase of the K dominating ...
93 views

### Does a non-constructive proof of bounds of a computable asymptotic complexity, with impossible fix, exist?

Does there exist an algorithm, about which a non-constructive $\omega$-consistent theory $A$ can prove that it has time complexity $O(f(n))$ where $n$ is some univariate function of the input, but ...
72 views

### Counting the maximum number of paths of length $n$ that differ in at least $k$ edges

What is known about the complexity of solving (or approximately solving) the following problem? INPUT: Graph $G=(V,E)$ and constants $L$ and $K$. OUTPUT: The maximum size of any set $S$ of simple ...
158 views

### Is it reasonable to allow the type of a λ/∀-bound variable to refer to itself?

Usually, in Pure Type Systems, the type of a λ/∀-bound variable is only accessible on its body. That is, on λ (X : A) -> B, <...
47 views

### Reduction of irregular graphs, to regular graphs, while preserving hamiltonicity

I am wondering if this is a topic that has had research done... If I could reduce irregular graphs to regular graphs (including replacing redundant node clusters with dummy nodes), while ensuring ...
87 views

### Complexity of solving a polynomial equation

Given a polynomial equation of degree n with m variables, that is guaranteed to have at least one solution, what is would be the ...
68 views

### Converting a propositional formula into an equisatisfiable CNF

For my homework I am asked the following question and determine whether it is true or false: Converting a propositional formula into an equisatisfiable CNF formula in the worst case requires ...