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.

learn more… | top users | synonyms

1
vote
2answers
109 views

Class of linearly parsable languages?

Is there name for class of languages exactly such that their words can be parsed in $O(n)$ by program in conventional Turing-complete language (SML)? (i.e. without backtracking) Any references?
0
votes
0answers
59 views

Survey of balanced languages/grammars etc

Is there any good survey of nested/balanced/parenthesed/bracketed/XML/Dyck/Floyd languages/grammars and their applications? If no, can you please list all relevant keywords to allow gathering all ...
0
votes
1answer
84 views

What is “language of words” means?

Some papers (especially about Nested Words languages) ofter contain term "language of words". What is the difference between "language" and "language of words"?
2
votes
2answers
311 views

Step function for greaterthan

I need to avoid using an if statement that does a $\geq$ comparison, (I'm writing HLSL code for the xbox). I need a function such that $f(x, y) = 0$ when $x < y$ and $f(x,y)=1$ when $x \geq y$. ...
1
vote
1answer
790 views

Proving regular expressions to be equivalent

I'm trying to prove that two regular expressions are equivalent. I mean prove in the rigorous sense of the word (i.e. this is a legit proof). The process is to show that R1 is a subset of R2, and ...
0
votes
1answer
242 views

Complementary language of a context free grammar

First post on Mathematics ;) I'm stucked with a problem related to automata theory / formal grammars. The problem ask the student to design a Pushdown automaton that accepts the complementary ...
5
votes
1answer
835 views

Easy proofs of the undecidability of Wang's tiling problem?

Wang tiles are (by Wikipedia): "equal-sized squares with a color on each edge which can be arranged side by side (on a regular square grid) so that abutting edges of adjacent tiles have the same ...
5
votes
2answers
772 views

Subset sum problem is NP-complete?

If I know correctly, subset sum problem is NP-complete. Here you have an array of n integers and you are given a target sum t, you have to return the numbers from the array which can sum up to the ...
4
votes
2answers
176 views

How do we know if a problem is hardest in NP

I read that the definition of NP-complete is : These are the hardest problems in NP. Such a problem is NP-hard and in NP How do we know if a problem is hardest in NP, and no harder problem ...
0
votes
1answer
132 views

Computational complexity of this algorithm

Consider a function $f(n,k)$ for $n,k\in\mathbb{N}$ and an algorithm that implements that function. The structure of the algorithm is as follows: do some calculations that take $O(n)$ time define ...
4
votes
3answers
479 views

NP hard/complete

I have never been very clear on this concept. Please help: At the end of the day, we should want to identify useful problems for which we don't have polynomial solution so far and only have ...
0
votes
2answers
401 views

How can I determine the cardinality of a set of polymorphic functions?

It seems obvious to me that the set of functions with the signature $\forall A. A \rightarrow A$ is "once-inhabited", i.e. there is only one such polymorphic function which "works" for any set $A$, ...
32
votes
6answers
2k views

Simple “real life” NP-hard problems?

There are many proofs lying around that games like Lemmings or Sudoku or Tetris are NP-hard (generalized version of those games, of course). The proofs, as I recall, are not difficult but not simple ...
3
votes
1answer
730 views

Determine if function is little-o, little-omega or big-theta

Let $f(n) = n^3(5+2\cos(2n))$ and $g(n) = 3n^2+4n^3+5n$. Given these two functions, I must determine the appropriate symbol where the underscore is: $f(n) \in \_(g(n))$ So, first thing to do is take ...
4
votes
2answers
178 views

Showing a property for a set of rewriting rules

Let $\to$ be a relation over the set of binary strings of 0 and 1. $\to$ is defined by the following rules: R1. $x10y \to x0001y $ R2. $x01y \to x1y $ R3. $x11y \to x0000y $ R4. $x00y \to x0y$ ...
4
votes
3answers
1k views

Proof Hampath is NP-Complete

I'm really confused by the proof that Hampath is NP-Complete. In order to prove something is NP-Complete, we can reduce another NP-Complete problem to it. So we want to take 3-SAT and reduce it to ...
2
votes
4answers
2k views

Example of a not recursively enumerable set $A \subseteq \mathbb{N}$

Can someone give me an example if a not recursively enumerable set $A \subseteq \mathbb{N}$ ? I came up with this question, when trying to show, that there exist partial functions $f: \mathbb{N} ...
8
votes
5answers
393 views

Is there any mathematical operation on Integers that yields the same result as doing bitwise “AND”?

I'll provide a little bit of a background so you guys can better understand my question: Let's say I have two positive, non-zero Binary Numbers.(Which can, obviously, be mapped to integers) I will ...
3
votes
1answer
360 views

pickup and delivery driver problem

Let's assume food delivery for multiple restaurants (say 20). There are (say 10) drivers available. Further, let's say we get 100 orders over a 4 hour period to deliver food from these restaurants to ...
1
vote
3answers
209 views

Algorithm to tell if a partial recursive function is 0 everywhere

Is there a (partial) recursive function that tells me, if a partial recursive function encoded by the number $c$ is the constant zero function ?
0
votes
1answer
165 views

Question about the “source code” of a recursive function

How can I show, that for every recursive function $f: \mathbb{N} \rightarrow \mathbb{N}$ we have a number (source code) $c$ such that $\forall x \in \mathbb{N}: f_U (c,x)=f_U (f(c),x)$, where $f_U: ...
3
votes
1answer
328 views

Partition a square into sub-rectangles with restrictions

Is there a method to generate all partitions of given square by using $n$ vertical and $n$ horizontal lines into sub-rectangles under the following restrictions? 1- No vertical line crosses any ...
5
votes
3answers
610 views

P vs NP and Gödel

I apologize for the, perhaps, silly question. My impression, as a layman, is that Gödel Incompleteness Theorem should rule out the possibility that P=NP. Is that true or there are deeper technical ...
3
votes
1answer
173 views

Is every recursively enumerable set $A \subseteq \mathbb{N}$ also recursive?

Is every recursively enumerable set $A \subseteq \mathbb{N}$ also recursive ? I'm not particularly interested in a detailed proof or counterexample, just a quick argument why this affirmation should ...
1
vote
1answer
201 views

If P/Poly does not contain NP then does SAT require super-polynomial circuits?

I have a basic question about circuit complexity. Apparently no example of a language that requires super-polynomial circuits to decide is known. (This is despite the fact that an easy counting ...
3
votes
2answers
590 views

How can I prove that this set is recursively enumerable?

Let $g _c (x)$ be the output of a program that is encoded by $c \in \mathbb{N}$ for the given input $x$. $g_c$ can obviously be undefined, in case the program encoded by $c$ doesn't halt. If we define ...
1
vote
1answer
63 views

Identities for relations of the form (a,b). If it holds, how do you “prove” it?

First some context (binary relations) $F \subseteq W \times X \quad G \subseteq X \times Y \quad H \subseteq Y \times Z $ Does the following equality hold $(G \circ F)^{-1} = F^{-1} \circ G^{-1}$ ...
3
votes
3answers
167 views

Why can't we diagonalize out, if we deal with partial functions?

We know, that all (partial) recursive functions are countable (since one can for example interpret them as some simple programs; and the set of those programs are themselves countable), so one can try ...
3
votes
1answer
140 views

Uniform PRNG for long integer structures

Good morning! I don't actually know where to attribute this question (maybe it's better to publish it on StackOverflow), but it's more related to math theory than to actual realization. Since the ...
2
votes
2answers
206 views

A Function That Creates “Hello World!” [closed]

The classic string "Hello world!" can be translated to list of characters with ascii-codes: [72; 101; 108; 108; 111; 32; 87; 111; 114; 108; 100; 33] Is there a ...
0
votes
0answers
122 views

Counting 1's with circuits

Let $M$ consist of the words in $\{0,1\}^{*}$, such that the number of $1$'s in $w$ is exactly $\lceil \log(n) \rceil$, where $n = |w|$. a) Design a sequence of circuits $C_n$ recognizing $M$. $C_n$ ...
2
votes
2answers
175 views

How do we know that there is a function from $\mathbb{N}$ to $\mathbb{N}$ that is not partial computable?

A partial computable function is also known as effectively computable, and is defined as any function that can be computed by a Turing machine with $Dom(f) \subseteq \Sigma^*$, where $\Sigma^*$ is the ...
0
votes
0answers
127 views

Terminology, mapping a tree to a tree

I have stumbled upon a problem, unfortunately I do not know the proper terminology to be used which hinders me in thinking about the problem and explaining the problem. I am not even sure this is the ...
4
votes
1answer
218 views

What is the power of a recursive language vs. that of one that is recursively enumerable?

I am simply wondering, as the title states, what the central differences are between recursive and recursively enumerable languages? If I am not mistaken a recursive language is a is Turing decidable ...
1
vote
1answer
894 views

Probability of collision in binary exponential backoff

Four stations are trying to transmit frames through a single channel (only one frame per channel). After each frame is sent, they contend for the channel using Binary Exponential Backoff. After ...
8
votes
5answers
450 views

What is a good language to develop in for simple, yet customizable math programs?

I'm writing to ask for some guidance on choosing a language and course of action in learning programming. I've seen thread after thread with questions from newbies, asking, "What is the best language ...
0
votes
2answers
147 views

Formal language problem

I’m new to formal language and searching for the solution for the following task: $\Sigma$ is an alphabet with $\lvert \Sigma\rvert = 5$ and $k \in \mathbb{N}_0$. I’m searching for $\lvert ...
0
votes
3answers
187 views

Formal language problem

Hello I´m new to formal language and searching the solution for the following task: Language: $L = \{0^{2i+1}|i\in\mathbb{N}_0\}$ Alphabet: $\Sigma = \{0\}$ I'm searching the resultion (sic) for: ...
6
votes
4answers
4k views

What does it mean to say a language is context-free?

What does it mean to say a language is context-free?
2
votes
3answers
143 views

Diagonalizations and their relation to P and NP

I'm quoting the following (landmark) paper: Theodore Baker, John Gill, and Robert Solovay Relativizations of the P?=NP Question SIAM Journal of Computing, Volume 4, Number 4, December 1975, ...
1
vote
2answers
121 views

On TM's with a single loop

Thinking about the halting problem for TM's, I came up with a statement that I can't prove or disprove easily and would want your suggestions. Conjecture: Given a TM whose digraph has a single cycle ...
5
votes
1answer
347 views

Rank of an interesting matrix

Lets define: $U=\left \{ u_j\right \} , 1 \leq j\leq N= 2^{L},$ the set of all different binary sequences of length $L$. $V=\left \{ v_i\right \} , 1 \leq i\leq M=\binom{L}{k}2^{k},$ the set of ...
8
votes
4answers
444 views

Consequences of solving the Halting problem

What impact would a device (ie super-computer or relativistic computer or other method) that solves the halting problem have on math? Would there be any mathematical problems left to solve? What ...
10
votes
4answers
525 views

What is undecidability

What does it mean that some problem is undecidable? For instance the halting problem. Does it mean that humans can never invent a new technique that always decides whether a turing machine will ...
1
vote
1answer
195 views

Does this number exist?

Consider the finite algorithm A, and the real number $0<T<1$. The output of A on input T is all possible theorems and provable propositions in ZFC, and only that. Q1. Can such an algorithm and ...
1
vote
3answers
203 views

Common algorithm with an order of Θ(2^n)

What would be a common algorithm with an order of Θ(2^n)? When I say "order", I mean time complexity analysis. I was thinking exponential growth but are there any that are more computer science ...
1
vote
3answers
158 views

Find the missing term

The sequence $10000, 121, 100, 31, 24, n, 20$ represents a number $x$ with respect to different bases. What is the missing number, $n$? This is from my elementary computer aptitude paper. Is there ...
0
votes
1answer
328 views

balanced 2-partition with equal cardinality (cardinality difference = 1 (max))

Given a set $S$ of $N$ numbers, my aim is to partition it into two sets ($S_1$ and $S_2$), so that (i) the difference $\sum S_1 - \sum S_2$ is minimized and (ii) the difference $|S_1| - |S_2|$ is ...
3
votes
2answers
304 views

How to solve recurrence relations with emphasis on algorithmic complexity

I am having trouble solving recurrence relations, probably because I am missing the basics. Is there any web reference/book I can read to help me cover the basics? I watched some lectures and read ...
8
votes
3answers
3k views

fast algorithm for solving system of linear equations

I have a system of linear equations, $Ax=b$, with $N$ equations and $N$ unknowns ($N$ large) If I am interested in the solution for only one of the unknowns, what are the best approaches? for ...