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

3
votes
2answers
115 views

A language that is not even context-sensitive?

Is there a language actually in use that can't be recognized by a linear bounded automaton? I only know of ones that don't have a practical use, like "the set of pairs of equivalent regular ...
6
votes
1answer
171 views

State of the progess of the automated proof checking

I recently came across a concept of automated proof checking. I am very intrigued by the idea, that in the future all the proofs could be verified by a computer. Moreover, some proofs were already ...
10
votes
3answers
281 views

Etymology of “topological sorting”

This may be a dumb question, but what's "topological" about topological sorting in graph theory? I thought topology was related to geometry and deformations.
1
vote
1answer
83 views

Show that $a^k w b^k$ when $|w|_a$ is divisible by $3$ is not regular

I want to show that $L = \{ a^k w b^k \mid k \geq 0, w \in \{a,b\}^*, |w|_a \text{is divisible by } 3 \}$ is not regular. I tried to use Pumping lemma as follows: Let $p$ be pumping length. $a^pb^p ...
2
votes
2answers
159 views

What is this proof syntax (Hoare 1974)?

I'm reading the seminal "Monitors" paper by Hoare. On page 4 he proceeds with a logical proof using syntax I've never seen before, and neither know what it's called or how to properly read it. ...
0
votes
1answer
225 views

Properties of a valid DFA

Is a DFA required to have transitions on each input symbol from each state defined? If there isn't a path from state q1 to another state on input a for example, does that invalidate the DFA itself. ...
2
votes
1answer
92 views

The study of Mathematical Visualization , Where Do I start?

I've looked through the literature on this topic , but it seems way to complex for me. I need some help , would you guide me through the process , from beginning to end.
1
vote
1answer
654 views

Partitioning a set of integers into 4 subsets with equal subset sums

Given $n (n \leq 20)$ positive integers and each integer is $\leq 10,000$. Can they be partitioned into $4$ subsets such that sum of the subsets are pairwise equal to each other. I am interested in ...
0
votes
0answers
96 views

Convert triangular real matrix to hermitian

We are developing some computer program which at some point uses a library (for which we do not have access to its source code) to solve the general eigenvalue problem; given two input real symmetric ...
3
votes
1answer
97 views

Treatments of Mahaney's Theorem?

Could you direct me to some readable treatments of Mahaney's theorem? The best thing I've been able to find is Fortnow's lecture. I'm especially interested in discussion around the theorem and its ...
3
votes
2answers
281 views

In what sense is “Uniform-cost search” uniform?

The name of Uniform-cost search in computer science is not instinctive since what part of it being "uniform" is not clear to me. Apparently uniformity is not about the cost of each edge - most of the ...
2
votes
1answer
287 views

To officially be recursion, must there be a base case?

In this Python code, the function f is defined, which then immediately calls itself: def f(): f() It's not very complicated, the first line defines the ...
11
votes
3answers
2k views

How to Prove a Programming Language is Turing Complete?

I had some thoughts about how to prove the turing completeness of a programming language. I came to the conclusion, that if you could write a program that is able to parse a turing machine program, ...
1
vote
1answer
147 views

Functional Completeness on 3-valued logic

I'm asked to prove by induction that a certain set of 4 function is complete on a 3-valued logic (Kleene). However, I'm having difficulty figuring out the induction step. More specifically, I'm not ...
1
vote
1answer
89 views

Regarding the definition of a problem

I recently noted from http://rjlipton.wordpress.com/2010/11/07/what-is-a-complexity-class/ that a problem is defined as a mere set of strings. So, here is the point: If I say the following: "Find ...
2
votes
0answers
127 views

1/3+2/3 in double precision

When I add 1/3 and 2/3 in double precision, I ended up with $1.\boxed{111\ldots1}1\times2^{-1}$, where the boxed part is the 52-bit mantissa. By the rounding to even rule, I should round it up, right? ...
1
vote
0answers
91 views

How can I create/modify 3-SAT functions according to Valiant-Varizani?

The Valiant-Varizani Theorem is given here. I also liked the description/proof given here - it's fairly straightforward. I've read these works, and I'm still very shaky with constructing new ...
3
votes
1answer
214 views

if P=NP, then is E=NE?

If the computational complexity class P equals to NP, does the complexity class E equal to the class NE? E is defined as $DTIME(O(2^{O(n)}))$ NE is defined as $NTIME(O(2^{O(n)}))$ Thank you very ...
2
votes
1answer
244 views

what is the relationship between the complexity class E(and EXP) and NP?

I want to know any relationship between the complexity class E(and EXP) and NP. I also would like to know whether there is any $DTIME$ formulation or relations of $NTIME(O(n^k))$ where n is the size ...
3
votes
1answer
67 views

Functions that are $\omega$(n)

Let $f(n) = \omega(n)$. Then for all constants $c > 0$ there exists a constant $n_0$ such that $f(n + 1) - f(n) > c$ for all $n > n_0$. The concept of Little-Omega is that the ...
2
votes
1answer
205 views

Halting problem and universality

Sorry this might be a layman question, but I could not find any information on this. Is the fact that there exists no Turing machine that can solve the halting problem equivalent to the existence of ...
0
votes
1answer
326 views

How to find bits you need to represent one variable? How many integers( 16 or 32 bits) you need when programming the problem?

Question: Use binary coded GA(Genetic algorithms), your problem is to find vector with real numbers $\in [0,5]$ and you want your answer at least to three decimal places(0.001). a) How many bits you ...
2
votes
1answer
137 views

Alternate expression for $e^x-1$

So if the following function is evaluated with the floating-point arithmetic, we get poor results for certain range of values of $x$. Therefore, I need to provide an alternate function that can be ...
3
votes
2answers
206 views

Alternate expression for the following function

So if the following function is evaluated with the floating-point arithmetic, we get poor results for certain range of values of $x$. Therefore, I need to provide an alternate function that can be ...
1
vote
2answers
141 views

Is Entscheidungsproblem in Co-RE? And Proof if it is.

As I study through, I learned that Entscheidungsproblem has a negative answer. Then I came to wonder whether the problem is in Co-RE. If it is, can anyone show me the proof? Thanks.
3
votes
1answer
335 views

How shall I understand this simple example of No Free Lunch theorem?

I have trouble in understanding a simple example following No Free Lunch theorem in James Spall's Introduction to stochastic search and optimization: My understanding is that a cost function is a ...
3
votes
0answers
89 views

Existence of a general-purpose (almost) universal optimization strategy

From Wikipedia about interpretations of no free lunch theorem A conventional, but not entirely accurate, interpretation of the NFL results is that "a general-purpose universal optimization ...
1
vote
4answers
674 views

Finite strings from infinite alphabet

Is the set of all strings of finite length $\Sigma^*$ from a infinite alphabet $\Sigma$ uncountable? The usual procedure in these types of proof is that you ...
0
votes
1answer
33 views

Covering Numbers of length 5 Radius 1

Can anyone give an example of 7 binary covering numbers that cover all 32 possible 5 digit binary numbers with an error of up to 1 place? I have proved that 6 binary numbers do not exist, but I am ...
2
votes
1answer
297 views

Understanding no free lunch theorem

From Wikipedia: $Y^X$ is the set of all objective functions $f$:$X$→$Y$, where $X$ is a finite solution space and $Y$ is a finite poset. The set of all permutations of $X$ is $J$. A random ...
3
votes
1answer
532 views

Visualizing Lattice Products

Partial orders can be thought of as a set $S$, and a partial relation on that set, $\le$. If a greatest lower bound and least upper bound exist for any subset of $S$, the poset defines a lattice. The ...
0
votes
2answers
71 views

Color Gradients

Say I have two Red Green Blue colors (255, 26, 26) and (241, 232, 91) respectively. If I'd like to determine the color halfway between these two colors, how could I solve for it? Is the answer simply ...
3
votes
1answer
239 views

What is the complexity of computing the minimum distance between two convex polyhedra that both have $n$ faces?

EDIT: (in response to what deinst said) sometimes using a sledgehammer for some menial task is rather convenient - especially if it also has the complexity $O(n)$ (which is what my question is about) ...
0
votes
1answer
384 views

Bitwise Operations: Collapsing two values into one.

Alright, so I'm having a hard time thinking of a way to do this. Perhaps someone here can help! Here is the problem: I need to figure out a way to use bitwise operations (or any sort of equation) to ...
2
votes
1answer
236 views

Size bound on regular expression describing language of an $n$-state deterministic automaton

The class of languages that can be recognised by some deterministic finite automaton is the same as those described by some regular expression. I evoked this well-known fact in class when discussing ...
1
vote
1answer
103 views

Help with the mathematical representation of operations on a matrix

I need to know how to represent the following as a mathematical formula using proper math notation: I have a $1\times n$-matrix of $3$-tuples $[a, r, x]$. I need to represent the following logic ...
1
vote
1answer
135 views

Converse of Gold's theorem and necessary condition for unlearnability

Background A class of languages $C$ has Gold's Property if $C$ contains a countable infinite number of languages $L_i$ such that $L_i \subsetneq L_{i + 1}$ for all $i > 0$ a further language ...
1
vote
1answer
172 views

Formula to compute number of groups from given points (with overlap)

The problem is kind of easy to understand. Given is some points, say 10 points. (I am using numbering for understanding) 0 1 2 3 4 5 6 7 8 9 Now group these such that the group size is 5 and there ...
2
votes
3answers
624 views

calculating unique value from given numbers

let's say I have some (n) random numbers 12, 13, and 18. I want to calculate some unique value from these three such that if I change their order 13, 12, 18 or 18, 12, 13..whatever order they are in, ...
7
votes
1answer
484 views

What is the best way to self-study GAP?

Background: This year I'll do another Group Theory course ( Open University M336 ). In the past I have used Mathematica's AbstractAlgebra package but (although visually appealing ) this is no longer ...
0
votes
1answer
180 views

Formula to browse through combinations

Can anyone give me an idea of how to be able to browse through a set of combinations? Lets say that I have 3 objects that can hold 3 different values and I want to browse through these. How do I know ...
1
vote
1answer
774 views

How many numbers are in a floating point number system, given these 4 parameters.

I'm trying to make floating point number systems a bit more intuitive for myself. There are a few things I am confused about, and I think the best way to clear up my confusions would be for someone to ...
5
votes
2answers
787 views

Why is integer factorization considered to be in NP if a quantum computer can compute a factorization in polynomial time?

Sorry if this seems off topic, the cstheory guys told me it was off topic over there, and sent me here. Shor's algorithm on a quantum computer can solve an integer factorization problem in polynomial ...
0
votes
1answer
123 views

Determining computational complexity of stochastic processes

I have an program which implements a Markov chain Monte Carlo process on a system of N bits, stopping when the process converges. Let's use T to denote the average number of steps made by the Markov ...
5
votes
0answers
326 views

how can i prove that square root of n is space constructible

I know that square-root of n is space-constructible. I can't prove it by the space-constructible definition. How can I show that only $\sqrt{n}$ space is used?
1
vote
1answer
219 views

If L is decidable and acceptable, is L' (complementary language) not-acceptable?

I know that if L is decidable and L' is acceptable, than L is not-acceptable. Is it also true to say that if L is decidable and acceptable, than L' is not-acceptable? I'm sorry if this question sounds ...
2
votes
3answers
201 views

Games with human edge [closed]

Which are some two- or one-player games, where humans far outperforms the best computer programs? And how does the relative edge scale with time allowed to think? (In time frame 1 sec to 8 hours per ...
0
votes
1answer
283 views

Is it always possible to convert a non-deterministic PDA to a deterministic one?

Is it always possible to convert a non-deterministic PDA to a deterministic one? What is the significance of this observation for the computing power of contex-free grammars?
2
votes
2answers
248 views

Universal Hashing

to my current understanding Universal Hashing is a method whereby the hash function is chosen randomly at runtime in order to guarantee reasonable performance for any kind of input. I understand we ...
0
votes
0answers
31 views

Some problem with function, operator, and optimization.

Actually, this problem come from a programming language challenge. The objective is: to create a one-to-one function, $f$, that mapped A into B with A = {0, 1, 2, 3, 4, 5, 6}, and B = {1, 5, 10, 50, ...