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

5
votes
4answers
219 views

Mathematics of computation

What is a good introduction to turing machines, complexity classes, P=NP etc from a purely mathematical viewpoint? I want to know how computation relates to provability in mathematics, I need the ...
1
vote
1answer
69 views

Algorithm to find nearest quotient in $\mathbb{Z}[i]$

Given two Gaussian integers $x$, $y$ what's the fastest way to find the Gaussian integer $z$ which minimizes $|x - zy|$? Then this Gaussian integer can be taken as $z = x/y$.
1
vote
1answer
160 views

Largest number definable

If $a_n$ is defined as the largest integer definable using $n$ characters in some standard theory like PA or $Z_2$. Can we prove or disprove that there is some finite integer $k$, such that for all ...
3
votes
3answers
9k views

Inverse of transformation matrix

I am preparing for a computer 3D graphics test and have a sample question which I am unable to solve. The question is as follows: For the following 3D transfromation matrix M, find its inverse. Note ...
1
vote
2answers
117 views

Halting problem confusion

Does the non-solvability of the halting problem mean that no program can tell if an arbitrary program halts, or only that if such a program exists then there is no computable proof that it works?
4
votes
1answer
121 views

What algorithms are there for determining whether a Gaussian integer is prime?

Give a Gaussian integer $z\in{Z[i]}$, how can I determine if $z$ is prime? I imagine there exists an algorithm that maps primality in $Z[i]$ to primality in Z. And for the case when $z\in{Z}$ I think ...
6
votes
3answers
157 views

Proving $\lim_{n\rightarrow\infty} n(2^{1/n} - 1) = \log 2$

How do you prove $\lim_{n\rightarrow\infty} n(2^{1/n} - 1) = \log 2$ ? Background: in computer science, if you allocate CPU time to $n$ processes by rate-monotonic scheduling, all the processes get ...
0
votes
1answer
286 views

Determining if language is context free

Is {xayb : x,y in {a,b}* and |x|=|y|} a context free language? My natural instinct would be to say that the answer is no, but can someone show me how to prove this?
4
votes
2answers
113 views

Where/What are good sources to learn about the history of computation?

I'm writing a giant paper containing the history of computation, and unfortunately, I'm far from being an expert on this. So far I have only a few sentences; I traced computation back to 3000BC, ...
10
votes
3answers
2k views

Proving that the halting problem is undecidable without reductions or diagonalization?

I'm currently teaching a class on computability and recently covered the proof that the halting problem is undecidable. I know of three major proof avenues that can be used here: Diagonalization - ...
1
vote
0answers
103 views

How are the various numbers in the standard 2.2 gamma correction for RGB derived?

Here is the standard fwd Gamma 2.22 (1 / 0.45) correction formula: ...
2
votes
1answer
101 views

A question about sorting

I've always been thought that the fastest way to sort an array of numbers has complexity $O(n \log (n))$. However, radix sort has complexity $O(kn)$ where $k$ is the number of bits. There are even ...
3
votes
1answer
110 views

Determining position at some point in time

I try to solve the following problem. On $n$ parallel railway tracks $n$ trains are going with constant speeds $v_1$, $v_2$, . . . , $v_n$. At time $t$ = 0 the trains are at positions $k_1$, ...
1
vote
2answers
277 views

Understanding Matrix Formula with Scant Knowledge of Linear Algebra

$n$ is a power of $2$. $M =\pmatrix{ 1& x_0 & x_0^2 & \dots &x_0^{n-1}\\\ 1& x_1 & x_1^2 & \dots &x_1^{n-1}\\&& \vdots\\1& x_{n-1} & x_{n-1}^{2} ...
5
votes
4answers
10k views

Intersection of two deterministic finite automata?

I'm trying to solve a problem where I have to create a DFA for the intersection of two languages. These are: $$\{s \in \{{\tt a}, {\tt b},{\tt c}\}^\ast : \mbox{every ${\tt a}$ in $s$ is ...
1
vote
1answer
137 views

Pumping lemma for regular “pumped formal language”

Let $\Sigma$ be an alphabet and $L\subseteq\Sigma^*$. We define $$\verb+lmult+(L)=\left\{x^iu\;|\;x\in\Sigma,u\in\Sigma^*,i>0,xu\in L\right\}\cup\{\epsilon\}.$$ [...] Show the ...
2
votes
1answer
329 views

Johnson-Cut Max-Cut Approximation

The Johnson-Cut is an $O(n^2)$ Max-Cut approximation with a factor of 2. I have these definitions for MC and none for JC so I assume they're the same: $G = (V,E,w)$ with $|V| = n$ and $w : E ...
12
votes
5answers
2k 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 ...
2
votes
2answers
166 views

Turing reduction

I'm learning algorithm theory. Homework question is: Are $A$ and $B$ possible so that $A\not\le_{tt}B$ (impossible to reduce using tt), but $A\le_T B$. But I can't think of any example..
2
votes
3answers
2k views

An algorithm to convert float number to binary representation

I want to know the algorithm of converting a given float (e.g, 3.14) to binary in the memory. I read this wikipedia page, but it only mentions about the conversion the other way. Let me quickly give ...
2
votes
0answers
88 views

Need little hint to prove a theorem .

I have an iterative method \begin{eqnarray} X_{k+1}=(1+\beta)X_k-\beta X_k A X_k~~~~~~~~~~~~~~~~~ k = 0,1,\ldots \end{eqnarray} with initial approximation $X_0 = \beta A^*$ ($\beta$ is scalar ...
7
votes
4answers
411 views

Big O Notation reliability?

Is Big-O notation always reliable? For example: Algorithm A: $n * 10^{100} = \mathcal{O}\left(n\right)$ Algorithm B: $n^{1.001} = \mathcal{O}\left(n^{1.001}\right)$ According to Big-$\mathcal{O}$ ...
3
votes
2answers
436 views

How to multiply two polynomials represented by values at distinct points?

I have two polynomials of degree $d$. However, I do not have equations for them. I simply have $d + 1$ distinct points on each polynomial. How would I find the product of these polynomials without ...
1
vote
2answers
85 views

non-complete problem collapsing to a lower complexity class complete problem

Let us say that there is a NP problem that is not a complete problem. And let us assume that someone found that the problem is in fact P-complete problem. Does this imply P=NP?
2
votes
1answer
442 views

Form or asymptotic behaviour of $T(n) =2T(n-1)+n$ [duplicate]

$T(n) =$ if $n=1$, then time execution is $1$, if $n \geq 2$ then $2T(n-1)+n$ The options are: $T(n) = 2^{n+1} - n - 2$ $T(n) = O(n2^n)$ $T(n) = \Omega(n)$ $T(n) = \theta(2^n)$ Thanks.
0
votes
1answer
69 views

Time to resolve a problem of size $1000$ in one second, how time take resolve the same problem of size $10.000$ in $n^2$?

A algorithm require one second to resolve a problem of size $1000$ a local machine. How long time take the same algorithm to resolve the same problem for a problem size of $10.000$ if the algorithm ...
0
votes
1answer
183 views

Master's Theorem?

When the ratio is $1$, why does the efficiency of the algorithm evaluate to $\mathcal{O} \left( n^d \log n \right)$? The total work done would be: $$T(n) = \mathcal{O}(n^d) (1+1+\cdots+1^k)$$ $$= ...
2
votes
2answers
178 views

is the language of Turing machine encodings context-sensitive?

Say we have an encoding of the set of all Turing machines/Turing programs -- WLOG, let's say the encoding takes values in the binary numerals. Call this set of binary numerals that represent Turing ...
4
votes
1answer
92 views

A logarithmic equation?

$$\mathcal{O} \left(3^{\log_2(n)} \right) = \mathcal{O} \left(n^{\log_2(3)} \right)$$ Does anyone have any idea how the right side was arrived at? (The $\mathcal{O}$ is Big-$\mathcal{O}$ notation)
0
votes
1answer
818 views

Visibility and Kernel of Polygon

I have an exercise to a give very rigorous prove to two observations of computation geometry. Obviously there are related. I've tried to prove them and wrote few ideas. Please take a look at them, and ...
1
vote
0answers
408 views

Polynomial-Time reduction: Clique Problem

Here is an exercise my friend proposed to me: Show that the maximum clique problem polynomial time reduces to the maximum independent set problem. Here is my attempt at solving it: It is known ...
3
votes
1answer
4k views

Why is this Parsing Expression Grammar left recursive?

I'm trying to get my parser generator to accept this specification. I know that's kind of a programming question, but I figured this was the best place to ask. It's specified as a Parsing Expression ...
2
votes
1answer
961 views

How to find best combinations of numbers to make the sums as close as possible.

Say I am given eight numbers: 10, 8, 8, 7, 6. 5, 5, 4 I am told to divide the group of numbers in to two different groups, four numbers each. What formula or method is there for running every ...
1
vote
4answers
176 views

A “State Hierarchy” Theorem for Turing Machines?

In complexity theory, there are time hierarchy theorems for Turing machines that show that for certain functions $f$, there exist problems that cannot be solved by a Turing machine in $o(f(n))$ time. ...
4
votes
1answer
95 views

How can one formalize and prove things about floating-point numbers, just as one can do with rational or real numbers?

Are floating-point numbers fundamentally different from the sets of rational or real numbers in any way? Are there any good mathematical treatments of floating-point numbers? Are they even interesting ...
3
votes
1answer
221 views

What am I describing - discrete continuity?

What area of math best describes continuous, but discrete changes in an object? For example. Example. If the start vector $(1,1,1)$ changed from itself to $(1,4,2)$ in one step, then since the ...
0
votes
1answer
1k views

Most computationally intensive algorithm.

I am trying to develop a benchmark to stress the CPUs on the Server for some HPC (High Performance computing) application. Please help me with some Algorithm that is believed to very CPU ...
0
votes
2answers
549 views

Relationship between XOR and “AND”

I want to XOR the password (0x3d), byte by byte, with 0x42, then 0x51, then 0xF7, then 0x6F. this would give me 0xb6..... But, Is there a shortcut to this operation?
2
votes
1answer
192 views

Longest cycle containing two nodes

We're given a directed unweighted graph $G = (V, E)$, with $|V| \leq 100$. The purpose of this problem is to find the longest cycle containing the two nodes $a$ and $b$. Only the length of that cycle ...
8
votes
3answers
411 views

“Phase change” of a purely mathematical system

Every so often I hear people talking about "phase transitions" in purely mathematical or computer-science contexts, where there is no physics in sight. Today, for example, I heard some people talking ...
2
votes
2answers
232 views

Finding similarities in an array in o(N*log N)

Given an integer N and an array of N real numbers (which you can compare and add/multiply/divide in O(1)), output 1 if there are two equal numbers and 0 else. This can easily be solved in O(N*log N) ...
1
vote
1answer
164 views

Solve equation on the PC

A friend of mine asked me to help him and make a small application to solve a problem. This problem can be reduced to this equation system: aX = Yb; Y > c; Y < d; X is a whole number (X has ...
0
votes
1answer
57 views

Question about the Smallest Grammar problem.

Is the problem to prove whether or not there exists an algorithm with running time polynomial in the length of the input string $|s|$, or polynomial both in $|s|$ and the size of the alphabet $|A|$ ? ...
1
vote
3answers
207 views

Finding a point above the line in $O(\log n)$

I am trying to solve the following problem. So far with no success. Let $S$ be a set of $n$ points in the plane. Preprocess $S$ so that, given a (non-vertical) line $l$, one can determine whether ...
1
vote
4answers
2k views

What is the runtime of a modulus operation

Hi I have an algorithm for which I would like to provide the total runtime: ...
3
votes
2answers
2k views

How do one-way functions work in cryptography?

Note: I wasn't sure of whether to ask this here, or on Security.se, but I am really looking for more of the mathematics side of it, so I decided to post it here I am looking to write my own ...
1
vote
1answer
84 views

Finding the computational complexity of an algorithm

Algorithm: for (int i = 0; i < 2*n; i += 2) for (int j = n; j >i; j--) foo(); I want to find the number of times foo() is called. ...
2
votes
1answer
306 views

Properties of shortest addition chains for small numbers (e.g. up to 600)

Up to which values of $n$ do the following properties hold for strictly monotonically increasing, shortest addition chains (sac) $a=a_1,\dots,a_k$ (definitions below)? a) There exists a sac for $n$ ...
0
votes
2answers
283 views

Algorithms for solving the discrete logarithm $a^x \equiv b\pmod{n}$ when $\gcd(a,n) \neq 1$

The general discrete logarithm problem is to find $x$ given $a, b$ and $n$ such that $$a^x \equiv b\pmod{n}.$$ Normally one can use the "baby-steps giant-steps" algorithm to solve it fairly quickly. ...
2
votes
1answer
310 views

Best and most efficient way to numerically compute $e$?

There are many well-known methods for efficiently numerically computing $\pi$, such as Chudnovsky's Method or perhaps Gauss-Legendre's algorithm. I was wondering what the best method for computing $e$ ...