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

132
votes
14answers
25k views

Is computer science a branch of mathematics?

I have been wondering, is computer science a branch of mathematics? No one has ever adequately described it to me. It all seems very math-like to me. My second question is, are there any books about ...
37
votes
2answers
1k views

Computation with a memory wiped computer

Here is another result from Scott Aaronson's blog: If every second or so your computer’s memory were wiped completely clean, except for the input data; the clock; a static, unchanging ...
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 ...
32
votes
3answers
1k views

Is the 24 game NP-complete?

The $24$ game is as follows. Four numbers are drawn; the player's objective is to make $24$ from the four numbers using the four basic arithmetic operations (in any order) and parentheses however one ...
28
votes
4answers
795 views

Why do we believe the Church-Turing Thesis?

The Church-Turing Thesis, which says that the Turing Machine model is at least as powerful as any computer that can be built in practice, seems to be pretty unquestioningly accepted in my exposure to ...
26
votes
6answers
3k views

Is the set of all valid C++ programs countably infinite?

I have heard that the set of valid programs in a certain programming language is countably infinite. For instance, the set of all valid C++ programs is countably infinite. I don't understand why ...
23
votes
12answers
3k views

How is the set of all programs countable?

I'm having a hard time seeing how the number of programs is not uncountable, since for every real number, you can create a program that's prints out that number. Doesn't that immediately establish ...
23
votes
1answer
621 views

Always oddly-many ones in the binary expression for $10^{10^{n}}$?

Update: Pending independent verification, the answer to the title question is "no", according to a computation of $q(10) = 11609679812$ (which is even). Let $q(n)$ be the number of ones in the ...
22
votes
5answers
4k views

Is a brute force method considered a proof?

Say we have some finite set, and some theory about a set, say "All elements of the finite set $X$ satisfy condition $Y$". If we let a computer check every single member of $X$ and conclude that the ...
19
votes
1answer
361 views

Mathematics of Torrenting

It is more or less common knowledge that a bittorrent network has the potential to be much faster than direct downloads, but I have never seen any real math describing why, or any theoretical bounds ...
17
votes
5answers
883 views

What interesting open mathematical problems could be solved if we could perform a “supertask” and what couldn't?

If we had a computer that could perform a countably infinite number of steps of a Turing machine, what currently open problems could we solve? I guess a lot of number theory problems could be solved ...
17
votes
2answers
2k views

Density of halting Turing machines

If we enumerate all Turing machines, $T_1$, $T_2$, $T_3,\ldots,T_n,\ldots$, What is $$\lim_{m\to\infty}\frac{\#\{k\mid k\lt m \text{ and }T_k\text{ halts}\}}{m}\quad?$$ Or does this depend on how we ...
17
votes
4answers
3k views

Number of ways to partition a rectangle into n sub-rectangles

How many ways can a rectangle be partitioned by either vertical or horizontal lines into n sub-rectangles? At first I thought it would be: ...
17
votes
1answer
401 views

Would relational calculus be Turing-complete if it allowed unsafe queries?

My understanding about Codd's concept of "safe queries" was created to ensure that a query would always terminate. One key ability of a Turing machine is that it can work on infinite calculations ...
16
votes
3answers
2k views

Is chess Turing-complete?

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff ...
16
votes
2answers
990 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 ...
15
votes
3answers
4k views

What are NP-complete problems and why are they so important?

I keep hearing questions about whether something is NP-complete, but they never really mention what it is. Why do people care so much about NP-complete problems?
15
votes
1answer
315 views

How to prove there are no more positive integers that are products of 2 and 3 consecutive numbers?

$6$ and $210$ share the property that both are the products of both two and three consecutive numbers. $6$ is $2\times3$ and $1\times2\times3$ and $210$ is $14\times15$ and $5\times6\times7$. It was ...
15
votes
6answers
711 views

What are the theorems of mathematics proved by a computer so far?

By theorems, I mean the ones you can find in an undergraduate course of mathematics, not the ones you can find in a textbook of automated proofs. I mean by "proved by a computer" that an existing ...
14
votes
6answers
3k views

The Practical Implication of P vs NP Problem

Although whether $$ P = NP $$ is important from theoretical computer science point of view, but I fail to see any practical implication of it. Suppose that we can prove all questions that can be ...
14
votes
2answers
625 views

In how many ways we can place $N$ mutually non-attacking knights on an $M \times M$ chessboard?

Given $N,M$ with $1 \le M \le 6$ and $1\le N \le 36$. In how many ways we can place $N$ knights (mutually non-attacking) on an $M \times M$ chessboard? For example: $M = 2, N = 2$, ans $= 6$ $M = 3, ...
13
votes
2answers
10k views

What books do you recommend before 'Concrete Mathematics'?

What book(s) do you recommend before Concrete Mathematics? Is something like "Introduction to discrete Mathematics" enough?
13
votes
6answers
2k views

What math should a computer scientist take in college?

I'm a computer science major and like many of us we have to take two additional sciences. These two additional science courses are in addition to three semesters of calculus,two semesters of physics, ...
13
votes
3answers
491 views

Curious Properties of 33

Because my explanation has so many words, I'll start with my question and then you can read the explanation if you need to: The Bernstein Hash method uses the number 33 as a multiplier. From what ...
12
votes
4answers
7k views

Do dynamic programming and greedy algorithms solve the same type of problems?

I wonder if dynamic programming and greedy algorithms solve the same type of problems, either accurately or approximately? Specifically, As far as I know, the type of problems that dynamic ...
12
votes
3answers
751 views

Twenty questions against a liar

Here's one that popped into my mind when I was thinking about binary search. I'm thinking of an integer between 1 and n. You have to guess my number. You win as soon as you guess the correct number. ...
12
votes
3answers
3k views

Ackermann Function primitive recursive

I am reading the wikipedia page on ackermann's function, http://en.wikipedia.org/wiki/Ackermann_function And I am having trouble understanding WHY ackermann's function is an example of a function ...
12
votes
4answers
182 views

How do you create a nonlinear game that the player can always win?

I thought a lot about this question — and initially, I intended to ask this on gamedev.stackexchange.com — but due to its rather theoretical aspects, I think it might be more appropriate to address a ...
12
votes
3answers
160 views

is there an efficient algorithm for comparing collections of points?

Let's say you have two sets of M points $p_1...p_M$, and $q_1...q_M$, which reside in $\mathbb{R}^N$. Is there an efficient (e.g. polynomial in M and N) algorithm to determine if the point-sets are ...
11
votes
3answers
271 views

What is necessary to exchange messages between aliens? [closed]

Lets assume that two extreme intelligent species in the universe can exchange morse code messages for the first time. A can send messages to B and B to A, both have unlimited time, but they can not ...
11
votes
3answers
311 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.
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, ...
11
votes
1answer
490 views

Assuming $P \neq NP$, do we know whether there are problems which are in $NP$, not in $P$ and are not $NP$ complete?

Here's a question. Have there been any theoretical results showing that if $P \neq NP$, there must exist some problems in $NP$ which are not $NP$-complete and which are not in $P$ either? Just ...
10
votes
3answers
1k views

Proving the Riemann Hypothesis without revealing anything other than you proved it

Consider the following assertion from Scott Aaronson's blog: Supposing you do prove the Riemann Hypothesis, it’s possible to convince someone of that fact, without revealing anything other ...
10
votes
4answers
596 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 ...
10
votes
3answers
578 views

Solving P vs NP with computer

Is it possible to build a computer program that would (eventually) bring a solution to the P vs. NP question?
10
votes
5answers
910 views

Why is convexity more important than quasi-convexity in optimization?

In the mathematical optimization literature it is common to distinguish problems according to whether or not they are convex. The reason seems to be that convex problems are guaranteed to have ...
10
votes
1answer
393 views

Fast inverse square root trick

I found what appears to be an intriguing method for calculating $$\frac{1}{\sqrt x}$$ extremely fast on this website, with more explanation here. However, the computer-science lingo and ...
10
votes
1answer
177 views

Is it possible that P != NP cannot be proved?

I am probably asking a stupid question but what I gather from a layman explanation of Godel's incompleteness theorem is that it is completely possible that a true statement cannot be derived from ...
10
votes
2answers
210 views

Applications of Geometry to Computer Science

How is differential geometry (or any type of theoretical math) being used in computer science? Any research I have done on this topic leads me to some sort of applied math concept. I know that there ...
10
votes
1answer
97 views

SQRTSORT from Vazirani's book on algorithms

I study the Algorithm book and saw the following exercise. I couldn't solve it. This is not homework, nor exam. Just reading some material on algorithms for preparing entrance exam. Any nice idea or ...
9
votes
2answers
689 views

Two $NP$-complete languages whose union is in $P$?

I've been thinking about transformations on $NP$-complete problems that produce languages known to be in $P$. However, I can't seem to find an example of two $NP$-complete languages whose union is in ...
9
votes
5answers
442 views

Prove that $ 1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n} = \mathcal{O}(\log(n)) $.

Prove that $ 1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n} = \mathcal{O}(\log(n)) $, with induction. I get the intuition behind this question. Clearly, the given function isn’t even growing ...
9
votes
3answers
215 views

Why isn't NP = coNP?

Suppose a language L is in NP. I think that means a nondeterministic Turing machine M can decide it in polynomial time. But then shouldn't it be in co-NP, because can't we define a new Turing machine ...
9
votes
4answers
496 views

If $P \ne NP$, is every language not contained in $NP$ $NP$-hard?

The other day, a student asked me whether, if $P \ne NP$, whether any language outside of $NP$ is known to be $NP$-hard. I wasn't sure if This is definitely known to be true, This is definitely ...
9
votes
4answers
579 views

An analog of the Myhill-Nerode Theorem for context-free languages?

The Myhill-Nerode Theorem gives an exact characterization of the regular languages. Given any language, one can check whether it meets the criteria of the Myhill-Nerode theorem to decide whether or ...
9
votes
3answers
644 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 ...
9
votes
2answers
456 views

Why is it undecidable whether two finite-state transducers are equivalent?

According to the Wikipedia page on finite-state transducers, it is undecidable whether two finite-state transducers are equivalent. I find this result striking, since it is decidable whether two ...
9
votes
1answer
417 views

Packing boxes and proof of Riemann Hypothesis

From Scott Aaronson's blog: There’s a finite (and not unimaginably-large) set of boxes, such that if we knew how to pack those boxes into the trunk of your car, then we’d also know a proof ...
9
votes
2answers
196 views

The mother of all undecidable problems

It is usual to show that a problem P is undecidable by showing that the halting problem reduces to P. Is it the case that the halting problem is the mother of all undecidable problems in the sense ...