# All Questions

41,885 questions
Filter by
Sorted by
Tagged with
390 views

### Concept of reduction and algorithm

Suppose that someone found an algorithm A for a NP problem (that is not NP-complete) that uses an algorithm B for PSPACE-complete or #P-complete problem during execution. (Remaining part of the ...
172 views

### Why is solving of diagonal quadratic equations over $\mathbb R$ and $\mathbb C$ in $P$?

Let $\mathbb F\in\{\mathbb R, \mathbb C\}$ the field of real or complex numbers. Then [1, page 22 in the middle] claims that the following equation can easily be solved in deterministic polynomial ...
19k views

### Left recursion and left factoring -- which one goes first?

if I have a grammar having a production that contains both left recursion and left factoring like $\qquad \displaystyle F \to FBa \mid cDS \mid c$ which one has priority, left recursion or left ...
4k views

### Are regular expressions $LR(k)$?

If I have a Type 3 Grammar, it can be represented on a pushdown automaton (without doing any operation on the stack) so I can represent regular expressions by using context free languages. But can I ...
296 views

### Vertex coloring with an upper bound on the degree of the nodes

Consider the set of graphs in which the maximum degree of the vertices is a constant number $\Delta$ independent of the number of vertices. Is the vertex coloring problem (that is, color the vertices ...
2k views

### Is Karp Reduction identical to Levin Reduction

Definition: Karp Reduction A language $A$ is Karp reducible to a language $B$ if there is a polynomial-time computable function $f:\{0,1\}^*\rightarrow\{0,1\}^*$ such that for every $x$, $x\in A$ if ...
703 views

### Time series probability and mutual information

There is a time series of say $100$ data points. I wish to assign symbols of $0, 1, 2$ for each unique data point. The issue is I have tried but got stuck since no matter I specify the symbols, the ...
1k views

### Lock-free, constant update-time concurrent tree data-structures?

I've been reading a bit of the literature lately, and have found some rather interesting data-structures. I have researched various different methods of getting update times down to $\mathcal{O}(1)$ ...
631 views

### Algorithm for type conversion / signature matching

I'm working on an expression typing system and looking for insights on what algorithms may be available which solve my problem -- or a proof that its complexity is too high to be reasonable to ...
286 views

### The $\text{k-key}$ problem

Given an undirected graph, I define a structure called k-key as a path containing $k$ vertices which are connected to a simple cycle which contains $k$ vertices as well. Here's the k-key problem: ...
548 views

### Existence of a route following one-way streets

I am trying to understand the approach for this problem: "If all streets are one way, there is still a legal way to drive from one intersection to another" The question is to prove that it can ...
250 views

### regular expression given the language

The language is: $$L = \{ (a^n) (b^m) \mid n + m = 3k, k \ge 0 \}$$ My attempt at an answer: $$(a \cup b)^{3k}$$ This will work if the a OR b can change for each instance in the string that is (...
1k views

### Prove that a boolean function computable in T(n) by a RAM machine is in DTIME(T(n)^2)

The question is exercise 1.9 from Arora-Barak's book Computational Complexity — A Modern Approach: Define a RAM Turing machine to be a Turing machine that has random access memory. We formalize this ...
7k views

### Is finding the longest path of a graph NP-complete?

The problem of finding the largest subgraph of a graph that has a Hamiltonian path can be restated as finding the longest path of a graph. Is this NP-complete? Also, is finding the $k$-length path of ...
10k views

### How hard is finding the discrete logarithm?

The discrete logarithm is the same as finding $b$ in $a^b=c \bmod N$, given $a$, $c$, and $N$. I wonder what complexity groups (e.g. for classical and quantum computers) this is in, and what ...
396 views

### Is the set of codes of Deterministic Finite-State Automata a regular language?

Let $\Sigma$ be a given alphabet. Is there a way to code up Deterministic Finite state Automata (DFA) over $\Sigma$ as strings of $\Sigma$ in such a way that the corresponding subset of $\Sigma^*$ is ...
194 views

### How do we distinguish NP-complete problems from other NP problems?

I just learned that when we have a polynomial algorithm for NP-complete problems, it is possible to use that algorithm to solve all NP problems. So, the question is how we then distinguish non-NP-...
3k views

### NP-completeness and NP problems

Suppose that someone found a polynomial algorithm for a NP-complete decision problem. Would this mean that we can modify the algorithm a bit and use it for solving the problems that are in NP, but not ...
535 views

### A regular expression for a given formal language

I wanted to ask if someone can help me to construct a regular expression over the alphabet $\{a,b,x\}$ for the language $L$ which is constituted by all strings containing an odd number of $a$'s, and ...
2k views

### Collectively pay the bill problem

There are $n$ people at a table. The $i$th person has to pay $p_i$ dollars. Some people don't have the right bills to pay exactly $p_i$, so they come up with the following algorithm. First, ...
384 views

22k views

### Prove that every two longest paths have at least one vertex in common

If a graph $G$ is connected and has no path with a length greater than $k$, prove that every two paths in $G$ of length $k$ have at least one vertex in common. I think that that common vertex ...
### Worst case $O(n \ln n)$ in place stable sort?
I am having trouble finding good resources that give a worst case $O(n \ln n)$ in place stable sorting algorithm. Does anyone know of any good resources? Just a reminder, in place means it uses the ...