All Questions

Filter by
Sorted by
Tagged with
8
votes
1answer
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 ...
10
votes
1answer
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 ...
25
votes
3answers
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 ...
2
votes
0answers
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 ...
4
votes
1answer
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 ...
5
votes
3answers
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 ...
12
votes
1answer
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 ...
2
votes
1answer
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* ...
3
votes
4answers
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 ...
16
votes
1answer
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 ...
12
votes
2answers
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 ...
19
votes
3answers
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 ...
4
votes
1answer
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.
26
votes
1answer
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 ...
3
votes
1answer
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$. ...
37
votes
4answers
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 ...
7
votes
1answer
523 views

Probabilistic test of matrix multiplication with one-sided error

Given three matrices $A, B,C \in \mathbb{Z}^{n \times n}$ we want to test whether $AB \neq C$. Assume that the arithmetic operations $+$ and $-$ take constant time when applied to numbers from $\...
8
votes
0answers
982 views

Weighted Maximum 3-DIMENSIONAL-MATCHING with restricted weights (Approx Algo)

If the weights of the weighted 3-DIMENSIONAL-MATCHING problem are restricted to let's say, 1 and 2, is there a possibility to reduce this case to the unweighted 3-DIMENSIONAL-MATCHING problem? (...
5
votes
2answers
157 views

Extracting non-duplicate cells in a particular matrix with repeated entries

Consider a board of $n$ x $n$ cells, where $n = 2k, k≥2$. Each of the numbers from $S = \left\{1,...,\frac{n^2}{2}\right\}$ is written to two cells so that each cell contains exactly one number. How ...
1
vote
2answers
364 views

From FACTOR To KNAPSACK

If there were an algorithm that factored in polynomial time by means of examining each possible factor of a complex number efficiently, could one not also use this algorithm to solve unbounded ...
8
votes
3answers
2k views

Key secrecy vs Algorithm secrecy

it's a well known statement that "Cryptographic security must rely on a secret key instead of a secret algorithm." I would like to ask about some details about it. And which are their differences? ...
5
votes
1answer
707 views

Fast Poisson quantile computation

I am seeking a fast algorithm to compute the following function, a quantile of the Poisson distribution: $$f(n, \lambda) = e^{-\lambda} \sum_{k=0}^{n} \frac{\lambda^k}{k!} $$ I can think of an ...
11
votes
1answer
3k views

subsets of infinite recursive sets

A recent exam question went as follows: $A$ is an infinite recursively enumerable set. Prove that $A$ has an infinite recursive subset. Let $C$ be an infinite recursive subset of $A$. Must $C$ ...
3
votes
1answer
7k views

Quicksort to find median?

Why is the worst scenario $\mathcal{O}\left(n^2\right)$ when using quicksort to find the median of a set of numbers? If your algorithm continually picks a number larger than or smaller than all ...
3
votes
2answers
1k views

Turn one string into another with single letter substitions

I want to turn one string into another with only single letter substitions. What is a good way to do this, passing through only valid words in between (this website has some examples)? Valid here ...
4
votes
2answers
1k views

$L(M) = L$ where $M$ is a $TM$ that moves only to the right side so $L$ is regular

Suppose that $L(M) = L$ where $M$ is a $TM$ that moves only to the right side. I need to Show that $L$ is regular. I'd relly like some help, I tried to think of any way to prove it but I didn't ...
-2
votes
1answer
13k views

Regular expression for all strings with at least two 0s over alphabet {0,1}

My answer : (0+1)* 0 (0+1)* 0 (0+1)* Why is this incorrect? Can somebody explain to me what the correct answer is and why?
17
votes
5answers
4k views

Are the functions always asymptotically comparable?

When we compare the complexity of two algorithms, it is usually the case that either $f(n) = O(g(n))$ or $g(n) = O(f(n))$ (possibly both), where $f$ and $g$ are the running times (for example) of the ...
31
votes
2answers
3k views

Why is a regular language called 'regular'?

I have just completed the first chapter of the Introduction to the Theory of Computation by Michael Sipser which explains the basics of finite automata. He defines a regular language as anything ...
4
votes
2answers
520 views

Counting trees (order matters)

As a follow up to this question (the number of rooted binary trees of size n), how many possible binary trees can you have if the nodes are now labeled, so that abc is different than bac cab etc ? In ...
7
votes
2answers
644 views

How many strings are close to a given set of strings?

This question has been prompted by Efficient data structures for building a fast spell checker. Given two strings $u,v$, we say they are $k$-close if their Damerau–Levenshtein distance¹ is small, i.e. ...
1
vote
1answer
472 views

Non-regular Languages? [duplicate]

Possible Duplicate: How to prove that a language is not regular? Why $L_a$ and $L_b$ are not reguluar? $L_a = \{ e^i f^{n-i} g^j h^{n-j} : n \in N, 1 \leq i, j \leq n \}$. $L_b= \{nm^{i_1} ...
4
votes
1answer
203 views

Explain $\log_2(n)$ squared asymptotic run-time for naive nested parallel CREW PRAM mergesort

On from Page 1 of these lecture notes it is stated in the final paragraph of the section titled CREW Mergesort: Each such step (in a sequence of $\Theta(\log_2\ n)$ steps) takes time $\Theta(\...
8
votes
0answers
197 views

Optimizing order of graph reduction to minimize memory usage

Having extracted the data-flow in some rather large programs as directed, acyclic graphs, I'd now like to optimize the order of evaluation to minimze the maximum amount of memory used. That is, given ...
14
votes
4answers
41k views

Dijsktra's algorithm applied to travelling salesman problem

I am a novice(total newbie to computational complexity theory) and I have a question. Lets say we have 'Traveling Salesman Problem' ,will the following application of Dijkstra's Algorithms solve it? ...
10
votes
2answers
360 views

How do I classify my emulator input optimization problem, and with which algorithm should I approach it?

Due to the nature of the question, I have to include lots of background information (because my question is: how do I narrow this down?) That said, it can be summarized (to the best of my knowledge) ...
5
votes
1answer
477 views

array median transformation using the min number of steps

Let $A[1...N]$ be an Array of size $N$ with maximum element $\max$. I want to transform array $A$ such that after transformations all elements of $A$ contain $\max$, i.e. after transformation $A = [\...
1
vote
1answer
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 ...
4
votes
2answers
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 ...
11
votes
2answers
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 ...
5
votes
3answers
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 ...
7
votes
1answer
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 ...
1
vote
1answer
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 ...
7
votes
1answer
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,...
5
votes
0answers
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 ...
4
votes
2answers
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 indefinitely. Wikipedia says space $O(n)$. How can this ...
3
votes
1answer
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 ...
14
votes
2answers
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?
4
votes
2answers
4k views

Why is this example a regular language?

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 ...
5
votes
2answers
4k views

Find the minimal number of runs to visit every edge of a directed graph

I am looking for an algorithm to find a minimal traversal of a directed graph of the following type. Two vertices are given, a start vertex and a terminating vertex. The traversal consists of several ...

15 30 50 per page
1
819 820
821
822 823
831