# All Questions

41,511 questions
Filter by
Sorted by
Tagged with
7k views

### NP $\subsetneq$ EXP?

I think I heard in somewhere that it has been proven that $\mathsf{NP}$ is strictly contained in $\mathsf{EXP}$, that is $\mathsf{NP} \subsetneq \mathsf{EXP}$. Is this right? Wikipedia and book ...
7k views

### How to prove that a constrained version of 3SAT in which no literal can occur more than once, is solvable in polynomial time?

I'm trying to work out an assignment (taken from the book Algorithms - by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Chap 8, problem 8.6a), and I'm paraphrasing what it states: Given that ...
11k views

### Pumping lemma for simple finite regular languages

Wikipedia has the following definition of the pumping lemma for regular langauges... Let $L$ be a regular language. Then there exists an integer $p$ ≥ 1 depending only on $L$ such that every ...
2k views

### Golden Section, Fibonacci and Dichotomic Searches

I wonder if somebody could quickly and briefly outline some of the similarities and differences between the line search methods Golden Section Search, Fibonacci Search and Dichotomic Search. I know ...
626 views

### A context free grammar proof

There is a problem which I cannot solve. If you give a tip I will be very glad. Prove that following language is not context free: $L= \{ a^nb^m | \gcd(n,m) = 1 \}$. It can be proven using the ...
4k views

### Counting different words in text using hashing

I am still fighting with hashing and I am ask myself: what is the most efficient way to count the number of different words in a text using a hash table? My intuition says that applying the hashcode ...
553 views

### What is complexity class $\oplus P^{\oplus P}$

What does the complexity class $\oplus P^{\oplus P}$ mean? I know that $\oplus P$ is the complexity class which contains languages $A$ for which there is a polynomial time nondeterministic Turing ...
4k views

### Nilsson's sequence score for 8-puzzle problem in A* algorithm

I am learning the A* search algorithm on an 8-puzzle problem. I don't have questions about A*, but I have some for the heuristic score - Nilsson's sequence score. Justin Heyes-Jones web pages - A* ...
8k views

### Why is $L= \{ 0^n 1^n | n \geq 1 \}$ not regular language?

I'm looking for intuition about when a language is regular and when it is not. For example, consider: $$L = \{ 0^n 1^n \mid n \geq 1 \} = \{ 01, 0011, 000111, \ldots \}$$ which is not a regular ...
217 views

### Polytime and polyspace algorithm for determining the leading intersection of n discrete monotonic functions

Some frontmatter: I'm a recreational computer scientist and employed software engineer. So, pardon if this prompt seems somewhat out of left field -- I routinely play with mathematical simulcra and ...
3k views

### An oracle to separate NP from coNP

How to prove that $\mathsf{NP}^A \neq \mathsf{coNP}^A$ ? I am just looking for a such oracle TM $M$ and a recursive language $L(M) = L$ for which this holds. I know the proof where you show that ...
3k views

### Maximum Enclosing Circle of a Given Radius

I try to find an approach to the following problem: Given the set of point $S$ and radius $r$, find the center point of circle, such that the circle contains the maximum number of points from the ...
268 views

### Mixed-strategy Nash equilibria

Is the following statement always true: if there is a mixed-strategy Nash equilibria then it is unique. I know that there can be several pure strategy Nash equilibrias.
1k views

### Is there a typed SKI calculus?

Most of us know the correspondence between combinatory logic and lambda calculus. But I've never seen (maybe I haven't looked deep enough) the equivalent of "typed combinators", corresponding to the ...
134 views

### An argument for error accumulation during complex DFT

I am doing FFT-based multiplication of polynomials with integer coefficients (long integers, in fact). The coefficients have a maximum value of $BASE-1, \quad BASE \in \mathbb{n},\quad BASE > 1$. ...
28k views

### Are there NP problems, not in P and not NP Complete?

Are there any known problems in $\mathsf{NP}$ (and not in $\mathsf{P}$) that aren't $\mathsf{NP}$ Complete? My understanding is that there are no currently known problems where this is the case, but ...
523 views

203 views

397 views

### Recursion for runtime of divide and conquer algorithms

A divide and conquer algorithm's work at a specific level can be simplified into the equation: $\qquad \displaystyle O\left(n^d\right) \cdot \left(\frac{a}{b^d}\right)^k$ where $n$ is the size of ...
353 views

### DFA with limited states

Lets $L_z \ := \{ a^i b^i c^i : 0 \leq i < z \}$ $\{a,b,c\} \in \sum^*$ there is a DFA with $\frac{z(z+1)}{2}+1$ states - How can I prove this? And I need largest possible number $n_z$, for ...
3k views

### Hashing using search trees instead of lists

I am struggling with hashing and binary search tree material. And I read that instead of using lists for storing entries with the same hash values, it is also possible to use binary search trees. And ...
2k views

### Proving that recursively enumerable languages are closed against taking prefixes

Define $\mathrm{Prefix} (L) = \{x\mid \exists y .xy \in L \}$. I'd love your help with proving that $\mathsf{RE}$ languages are closed under $\mathrm{Prefix}$. I know that recursively enumerable ...
257 views

### What techniques exist for energy-efficient computing and networking?

I am currently reviewing the potentials of cloud computing regarding energy efficiency and green IT. In connection with this review I am having a look on techniques for increasing energy-efficiency in ...
57 views

### How will broadcast behave with a certain capacity?

I wanted to confirm something and will appreciate your help. Suppose we have three nodes called A,B and C. All are connected to a switch whose port supports 1 Gbps. Now suppose, Node's A network card ...
15k views

### how do you prove that SAT is NP-complete?

As it is, how do you prove that SAT is NP-complete? I know what it means by NP-complete, so I do not need an explanation on that. What I want to know is how do you know that one problem, such as SAT,...
38 views

### Uni-directional synchronization and locking issues

Suppose there are two databases, $D_1$ and $D_2$. Let's further assume $D_1$ is always up and $D_2$ can be down sometimes. When it goes up again, it has to restart. $D_1$ is filled by say a dozen ...
979 views

### Expected space consumption of skip lists

What is the expected space used by the skip list after inserting $n$ elements? I expect that in the worst case the space consumption may grow indeﬁnitely. Wikipedia says space $O(n)$. How can this ...
132 views

### Randomized String Searching

I need to detect whether a binary pattern $P$ of length $m$ occurs in a binary text $T$ of length $n$ where $m < n$. I want to state an algorithm that runs in time $O(n)$ where we assume that ...
536 views

### Organisation and Architecture of Quantum Computers

What are devices and their interconnections used alongwith Quantum Processors? Are they compatible with hardware devices like Cache, RAM, Disks of current computers?
Consider this example (taken from this document: Showing that language is not regular): $$L = \{1^n \mid n\text{ is even}\}$$ According to the Pumping Lemma, a language $L$ is regular if : \$y \ne ...