All mathematical questions about computer science, including theoretical computer science, formal methods, verification, and artificial intelligence. For questions about Turing computability, please use the (computability) tag instead. For numerical analysis, use the (numerical-methods) tag. For ...

learn more… | top users | synonyms

16
votes
2answers
1k views

What is the complexity of succinct (binary) Nurikabe?

Nurikabe is a constraint-based grid-filling puzzle, loosely similar to Minesweeper/Nonograms; numbers are placed on a grid to be filled with on/off values for each cell, with each number indicating a ...
7
votes
2answers
2k views

Dijkstra's algorithm using heap

My teacher gave me a pseudocode of Dijkstra's algorithm using binary heap including the following steps (x was just extracted from the heap): For each vertex y such that it is a node for it in a ...
5
votes
2answers
918 views

Is this function a primitive recursive function?

Let $t \in \mathbb{N}$ and consider the function $f: \mathbb{N} \rightarrow \mathbb{N}$, defined by $f_t (m)= 2 \uparrow^{m} t$, where "$\uparrow$" is Knuth's up-arrow notation (which can be ...
0
votes
1answer
57 views

Probabilistic performance guarantees on information retrieval queries

The following is a question from lecture notes and although not assigned homework, I am trying to solve it. Assume that we have a collection $C$ of $N$ documents and a query $q$. There are $R_{q}$ ...
10
votes
1answer
758 views

Incremental calculation of inverse of a matrix

Does there exist a fast way to calculate the inverse of an $N \times N$ matrix, if we know the inverse of the $(N-1) \times (N-1)$ sub-matrix? For example, if $A$ is a $1000 \times 1000$ invertible ...
1
vote
1answer
217 views

Rank of a graph matrix

$G$ is a bipartite graph with $2m$ nodes on the left $(u_0..u_{2m-1})$, and $2^{m}$ nodes on the right $(v_0..v_{2^{m}-1})$. There is an edge (connection) between $u_i$ and $v_j$ iff $(i+1)$'th ...
5
votes
2answers
4k views

How to show that $ALL_{DFA}$ is in P

How can I show that $ALL_{DFA}$ is in P ? $ALL_{DFA} = \{ \langle A \rangle \mid A \text{ is a DFA and } L(A) = \Sigma^* \}$
2
votes
2answers
325 views

Recognizing language using Turing machine

Given integers $a, b, c$ construct a single-tape Turing machine recognizing the language $\{w \in \{0,1\}^{*}: a*\#_{0}w+b*\#_{1}w+c=0\}$ in time $O(n*logn)$, where $n=|w|$. $\#_{x}w$ denotes the ...
2
votes
1answer
333 views

Detecting cycles in off-line Turing machines

Let $M$ be an off-line Turing machine over the input alphabet $\{0,1\}^{*}$, that uses only one working tape in addition to the input tape. Construct a Turing machine $M'$, such that: $L(M) = L(...
6
votes
2answers
478 views

Faulty proof of polynomial hierarchy first level collapse?

I am an undergraduate of CS and I participate in TCS.SE. I am having trouble finding the error in a proof about the polynomial hierarchy collapsing to the first level ($NP = coNP$). I believe the ...
9
votes
3answers
745 views

NP vs NP-Complete

Is there any problem which is in NP but not in NP-Complete? Is there any possibility that this problem is analogous to P=NP problem, if so is there any problem which is in NP, but currently there is ...
2
votes
1answer
418 views

Proving problems are unsolvable - reducibility proof

Suppose we have P, a string denoting a C program which takes in a natural number as input and outputs at most one natural number. Prove that it is impossible (unsolvable) to determine that P has ...
2
votes
1answer
633 views

Considering math or computer science

Let me start by saying I graduated High School in 2002 and have worked as a technician, a systems administrator, and a part time web developer up till now. I have started taking courses at community ...
4
votes
1answer
2k views

How do you do a cross product of two $3 \times 3$ boolean matrices?

I have two boolean matrices: A = |1 1 0| |0 1 0| |0 0 1| and B = |1 0 0| |1 1 1| |0 0 1| What is the result of A x B and what are the steps ...
18
votes
2answers
24k views

Recognizable vs Decidable

What is difference between "recognizable" and "decidable" in context of Turing machines?
1
vote
2answers
585 views

Running 'Encrypted Code' on a Computer

Alice released a new version of her software for removing red-eye from pictures. However, she wants to protect her secret algorithm from disassemblers and such while still letting her customers remove ...
8
votes
1answer
361 views

is this language context free? [closed]

I need an NPDA for the following language if it is context-free, and if it isn't I need a proof using the pumping lemma that it is not a CFL: $$L_1=\{w_1w_2 \in \{a,b\}^* : |w_1| = |w_2|,w_1\neq w_2\}...
3
votes
2answers
955 views

Proving insertion sort using induction

A while back when I was taking a first year cs course, our professor had us write the algorithm for insertion sort in The Scheme programming language. There were also several other similar recursion ...
0
votes
2answers
99 views

Mapping between random strings?

Let us define a one-to-one function $f$ that maps binary strings of length $n$ to ternary strings of length $n$ such that if $x$ is random then $f(x)$ must be random. My question Is there an ...
4
votes
1answer
398 views

Decidable? Turing machine runs X steps for certain input?

Question is the following language decidable: {(M)|given input "aaaaa" Turing machine M will perform at least 1295 steps} I would say, yes it is. Just let the Universal Turing Machine count each ...
1
vote
1answer
250 views

Is language L context-free?

Is following language context-free? Alphabet: {a,b,c,d} L = {w | w is not in {aabbc,abc,add}} I think it is: {aabbc},{abc},{add} are all regular. Because of closure properties(Union) R = {w | w ...
3
votes
2answers
314 views

L* regular -> L regular?

If language L* (Kleene Star) is regular, does it imply that L is also regular?
3
votes
1answer
847 views

Turing machine configuration and computation history

These are a series of questions about Turing machines. First, are the number of a given Turing machine configurations (state + tape) countable? Secondly, given that a computation history is a ...
6
votes
1answer
663 views

Are there any known barriers to some approach for solving P vs. NP?

Are there any known barriers to show the following invariant (perhaps by some sort of induction)? Let $\Sigma$ be some finite alphabet with $|\Sigma| \geq 2$, let $M$ be some (deciding) deterministic ...
4
votes
1answer
341 views

Cantor–Bernstein–Schröder theorem and recursion

I am poking on a proof of the subject theorem. Given sets $A_i$ and injections $f_i:A_i\to A_{1-i}$, $i\in \{0,1\}$, theorem defines a bijection $b$ between $A_0$ and $A_1$. $b$ uses an auxilary ...
4
votes
2answers
192 views

Many one and One many reductions

I do not have enough complexity theory background, but I was wondering about the kind of reductions that we normally do to show NP-Completeness. I think all of the reductions that I have seen are one-...
1
vote
2answers
282 views

Is this DFA correct

I'm supposed to construct a DFA which accepts { w | w is a word except 'aa' and 'aaa' } Is this the correct solution? The thick line state is supposed to be the end state. EDIT Sry, somehow ...
2
votes
2answers
5k views

Understanding $\epsilon$ transitions in a finite state automaton

I am trying to understand how $\epsilon$ transitions work. From what I've read, when you "go" to a state S that has arrows pointing outwards with $\epsilon$'s in it, you automatically go to those ...
0
votes
1answer
268 views

Question about ambiguity of BNF

The BNF is defined as follows: <S> -> <S>a<S>a<S> | b This is my review question for a quiz, and according to my teacher, this grammar ...
1
vote
1answer
830 views

Independent Set decision problem in P

If P=NP, is there a polynomial-time algorithm $A$ that can decide the $\text{Independent Set}$ decision problem? That is, with an undirected graph $G = (V, E)$ and a positive integer $k$, does $G$ ...
3
votes
3answers
3k views

Proving that $|xy| = |x| + |y|$ being $x$ and $y$ two strings

I am to prove that being $x$ a string and $|x|$ its length, one should have the following property hold true for any two strings $x$ and $y$: $$ |xy| = |x| + |y| $$ with $x, y \in \Sigma^*$. To ...
2
votes
1answer
2k views

Nondeterministic Finite Automata to Deterministic Finite Automata?

I am unfamiliar with the general process of converting NFA to DFA. I have general understanding of the theory, but I don't have the method established. Please help explain the process required to ...
4
votes
1answer
182 views

Help understand $\text{handle}$ in parsing problem

The BNF is defined as followed: S -> aAb | bBA A -> ab | aAB B -> bB | b The sentence is: aaAbBb And this is the ...
4
votes
3answers
1k views

Is this BNF grammar ambiguous?

I have a BNF defined as follow: <S> -> 0 <S> -> 1 <S> -> <S><S> I think this grammar is not ambiguous, but the solution ...
1
vote
1answer
191 views

Need help explain BNF

I have several BNF defined as follow: ...
4
votes
1answer
134 views

Do there exists permutations $\pi_1,\pi_2$ and polynomial size CFG that describe the finite language $\{w \pi_1(w) \pi_2(w)\}$ over alphabet {0,1}?

Do there exists permutations $\pi_1,\pi_2$ and polynomial size CFG that describe the finite language {$w \pi_1(w) \pi_2(w)$} over alphabet {0,1}? Polynomial size in $|w|=n$
3
votes
1answer
105 views

An efficient way to check whether a polynomial (under certain condition) is absolutely equal to zero or not

We have a function $f$ of $N$ variables which is the product of $M$ polynomials: $$f(x_1,x_2,\ldots, x_N) = P_1 \cdot P_2 \cdots P_M.$$ Each $P_i$ is a polynomial of at most three variables ($x_j$s)...
2
votes
1answer
81 views

a function of a dependent type, a section, a sheaf

I have defined this simple sheaf. Take $E:set, B:set, p:E\to B$. Let $P(B)$ be a set of subsets of $B$. Let $S$ be the set of sections of $p$. Let $F$ be a contravariant functor from $P(B)$ as a poset ...
0
votes
1answer
61 views

Language complexity from instances of graph

Let $G$ represent an undirected graph, let $a$ and $b$ represent vertices and let $k$ represent a non-negative integer. I have two languages: $L_1 = \left \{ \left \langle G, a, b, k \right \...
5
votes
1answer
706 views

Proof by double induction on strings (SOLVED)

I am truly baffled as to go on to prove this by double induction: http://i.stack.imgur.com/Zvrzt.png (snap shot of question) This question seems rather trivial on first glimpse, however trying ...
6
votes
3answers
853 views

Is learning haskell a bad thing for a beginner mathematician?

Haskell is a programming language which uses some concepts from category theory like functor, monad, etc. My question is: Learning intuitive concepts about category from Haskell will ruin my intuition ...
7
votes
1answer
506 views

Importance of Constructible functions

A function $f$ is called fully time-constructible if there exists a Turing machine $M$ which, given a string $1^n$ consisting of $n$ ones, stops after exactly $f(n)$ steps. Analogously, we can call a ...
1
vote
2answers
151 views

Nondeterminism and computational models

So it is clear than the nondeterministic versions of computational models such as the Turing Machine is equivalent in "power" to the deterministic model. Other than showing this fact, what would be ...
5
votes
2answers
3k views

What is the current status of Vinay Deolalikar's proof that P is not equal to NP

This could be mathematics or computer science, but also statistical physics, so I hope it qualifies for interest :) I am aware that there were reservations about the proof but no fatal flaws. I have ...
3
votes
3answers
292 views

Software/algorithm for the smallest context free grammar describing a set of words?

I am looking for software/algorithm for the smallest context free grammar describing a finite set of words (and no other words). For a single word I found sequitur Related to this seems: given a CFG ...
3
votes
1answer
111 views

Does fixing the number of elements in PARTITION send it in P?

It's possible that this question is trivial and I've overlooked something. Let us impose the following constraint on the well-known PARTITION problem: in all inputs of a new problem the number of ...
1
vote
1answer
312 views

Counting the number of asymmetric graphs on n nodes?

Asymmetric graph is a graph that has only trivial automorphism. Asymptotically, almost all finite graphs are asymmetric. I'm looking for upper bounds and lower bounds on the growth rate of the number ...
1
vote
1answer
293 views

Can a polynomial size CFG describe the finite language \{$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed\} over alphabet \{0,1\}?

Can a polynomial size Context free grammar describe the finite language {$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed} over alphabet of {0,1}? One case this is possible is when ...
0
votes
1answer
157 views

Problem k-subvector using dynamic programming

Given a vector V of n integers and an integer k, k <= n, you want a subvector (a sequence of consecutive elements of the vector ) of maximum length containing at most k distinct elements. The ...
2
votes
1answer
1k views

Solving a nonlinear system using Groebner basis computations

I have discovered that Groebner basis computations may help in a problem I am working on. However, I am having some very specific problems. First, the literature I have discovered on Groebner basis ...