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
3answers
267 views

categorization of logic

(1). I was wondering about what are the relation and differences between formal and informal logic? What topics does each of them have? For example, topics such as Meaning and Definition, Syllogistic ...
1
vote
0answers
58 views

Who uses R with multicore, SNOW or CUDA package for resource intense computing?

who of you in this forum uses R (http://www.r-project.org/) with the multicore, SNOW or CUDA packages, so for advanced calculations that need more power than a workstation CPU? On which hardware do ...
2
votes
2answers
232 views

Does this proof for the undecidability of the halting problem violate the axiom of regularity?

One proof of the halting problem goes by contradiction like this : Assume there is a Turing machine $H$ that can decide the halting problem, then construct a Turing machine $Q$ that takes as input a ...
1
vote
2answers
399 views

shadow simulation from buildings

is it possible to calculate shadow areas of buildings or simulate shadows of buildings in a city, using the heights of these buildings and the sun angle and azimuth? the basic light tracing concept ...
3
votes
0answers
126 views

Hardness of perimeter minimization?

Given $xy=C$ where $x, y$ are integer variables and $C$ is integer constant. What is the most efficient algorithm that finds $x,y$ such that $x+y$ is minimum? Providing references is highly ...
6
votes
2answers
577 views

Looking for a bijective, discrete function that behaves as chaotically as possible

I need to write a coupon code system but I do not want to save each coupon code in the database. (For performance and design reasons.) Rather I would like to generate codes subsequent that are ...
0
votes
1answer
715 views

How to calculate daily user churn rate?

I have a table in my database that records, 48 times per day, the total users, total active users within 2 weeks, total users logged in within the past 24 hours , and total users that logged in within ...
1
vote
3answers
1k views

What are the prerequisites for combinatorics?

I'm looking to strengthen my understanding of the math that is directly useful to practical computer science, as opposed to unsolved computer science problems. In other words, the kind of math that ...
1
vote
1answer
100 views

Problem interpretation - Distance Formula?

If you've got multiple arrays like this: (24,36,28,28,16,27) (38,38,45,57,35,50) every array being 6 integers, each integer in range [0,60] I would like to find the distance between those 2 ...
5
votes
2answers
410 views

What requirements should a CRC polynomial satisfy?

What requirements should a CRC polynomial of a given degree satisfy to make the CRC catch a maximum of errors? edit I'm talking about GF(2) polynomials. As an example of the kind of requirements ...
4
votes
3answers
5k views

Reduction from Hamiltonian cycle to Hamiltonian path

I'm looking for an explanation on how reducing the Hamiltonian cycle problem to the Hamiltonian path's one (to proof that also the latter is NP-complete). I couldn't find any on the web, can someone ...
3
votes
3answers
709 views

Applications of Logic and Algebra in Computer Science

I have used logic for specification of security policies in a security model. One of my reviewers asked a question that "why did you use logic and not algebra for this purpose, and what is your ...
1
vote
1answer
142 views

Related Integer Combination

The title and tags are a little goofy since I'm not quite sure what to call this. This may be more of a computer science question, but I thought I'd ask here too. I have two integers n and m that ...
4
votes
1answer
180 views

Complexity - why is RL=NL when omitting the demand for polynomial run-time?

The complexity class RL is described at the complexity zoo as: Has the same relation to L as RP does to P. The randomized machine must halt with probability 1 on any input. It must also run in ...
3
votes
1answer
188 views

The Hamiltonian problem on Polyominoes

A polyomino is a connected subset of $\mathbb{Z}^2$ - a set of squares joined along their edges such that the resulting form is connected (or, more shortly, a generalized form of Tetris cube). A ...
5
votes
2answers
318 views

Question about the P versus NP Problem

It seems to be an accepted belief based on decades of experience that naive algorithms are not adequate to solve NP-complete problems in a reasonable amount of time. Even those who believe P = NP ...
3
votes
2answers
2k views

How to prove the optimal Towers of Hanoi strategy?

In the towers of Hanoi game, how do we know that we have the optimal algorithm for solving it? I thought about this and it seemed like any deviation from the standard strategies would be putting you ...
11
votes
1answer
465 views

Assuming P != 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 != NP, there must exist some problems in NP which are not NP-complete and which are not in P either? Just curious because ...
1
vote
3answers
234 views

Calculate integer summation when lower bound is a variable

How do you calculate the following summation? $\sum_{i=k}^n i$
12
votes
6answers
2k 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 ...
3
votes
2answers
91 views

How do I calculate a specific variation for a known value of the normal distribution function?

I am writing a Gaussian blur filter in graphics shader code. I want to make the blur parameterized by radius from the users perspective. The best method I can figure to do this is to pick a suitable ...
6
votes
3answers
4k views

Lower bound for finding second largest element

In a recent discussion, I came across the idea of proving a lower bound for the number of comparisons required to find the largest element in an array. The bound is $n - 1$. This is so because the set ...
2
votes
2answers
301 views

'(Pseudo)-random functions' by seeding of PRNGs?

I have an application that wants controllable random functions from $\mathbb{Z}^2$ and $\mathbb{Z}^3$ to $2^{32}$ , where by controllable I basically mean seedable by some parameters (say, on the ...
1
vote
2answers
306 views

Time complexity to find the extremal value of a function

Let $O(f(n))$ be the minimum time complexity for output a real sequence ${a_i}$. The input of the algorithm is a integer $n$. It output the finite sequence $a_1, a_2, \ldots, a_n$. (Clearly $f(n)\geq ...
0
votes
1answer
124 views

What is computational geometry and who should take a course on this subject? [closed]

In mathematics, geometry is the topic I like. Just out of curiosity I would like to know what computational geometry is about. Who studies this subject and why. What are its applications, or is it ...
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: ...
7
votes
1answer
386 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 ...
36
votes
2answers
893 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 ...
9
votes
3answers
923 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 ...
5
votes
2answers
498 views

What is the best way to factor arbitrary polynomials

I am currently working on a Computer Algebra System and was wondering for suggestions on methods of finding roots/factors of polynomials. I am currently using the Numerical Durand-Kerner method but ...
12
votes
3answers
668 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. ...
6
votes
3answers
979 views

What is linear programming?

I asked this question on Stack Overflow but it was closed as "not programming related". So I think this is probably the best place for it... I read over the wikipedia article, but it seems to be ...
13
votes
3answers
3k 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?
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 ...
13
votes
1answer
315 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 ...