# Questions tagged [computer-science]

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 questions from scientific computing, use (computational-mathematics).

5,453 questions
Filter by
Sorted by
Tagged with
209 views

### Compute the Googolplex-th Fibonacci number modulo $10^9+7$

Is it possible to find this in a reasonable amount of time? The best theoretical approach that I’m aware of is using the Fibonacci Matrices, but even at a complexity of $O(\log n)$, the logarithm of a ...
1 vote
23 views

### Will this attempt to mathematically formalize the Burrows Wheeler Transform (BWT) let us define generalizations or variations of it?

Background: The Burrows-Wheeler Transform (BWT) is an a mathematical transform traditionally defined on strings of letters and used in signal processing for example for data compression purposes. Here ...
138 views
+50

### Prove that co-NP is closed under ≤k.

Using if $B \in \mathsf{coNP}$ and $A \leq_k B$, then $A \in \mathsf{coNP}$ I was trying to use Since $B$ is in $\mathsf{coNP}$, there exists a polynomial time verification algorithm $V$ such that: ...
34 views

### Applications of category theory in Computer Science and Mathematical Physics. [closed]

Could someone name some examples where we make use of category theory in Computer Science or Physics, specifically in Mathematical Physics?
32 views

### Second place in the Turing Machine race

Given a deterministic Turing machine T which begins on an infinite blank strip, let its growth rate $G_T(t)$ represent the number of non-blank squares after the machine is run for $t$ time steps. It ...
16 views

### Inverting a Large Amount of Block Matrices which Develop a Global Pattern

Essentially, I am running an algorithm where I create some matrix G. When I work G on small systems it is not apparent that there is any pattern within G. However, when G becomes sufficiently large it ...
1 vote
33 views

### Computational complexity of colored vector space isomorphism over the binary field

Suppose there are two vector spaces $V$ and $W$ of the same dimension $n$ over the binary field $\mathbb{Z}_2$ together with subsets $S_V$ and $S_W$ of $V \setminus \{0\}$ and $W \setminus \{0\}$, ...
1k views

### How is GNFS the best factoring algorithm when its time complexity exceeds brute-force?

While researching another problem, the Sieve of Eratosthenes got me wondering why it couldn’t be used to factor. After playing around, I stumbled upon an algorithm that seems like it should find ...
1 vote
52 views

### Algorithm analysis - when to throw away terms?

In this algorithmic analysis of least squares regression, we throw away big-$O$ terms that will be dominated by the biggest, and keep only the dominant term. On the other hand, in this algorithmic ...
1 vote
70 views

### How to apply the log sum exp trick on the following expression?

I am an electrical engineer who is currently working with some probability problem. In my expression, I experience some numerical error for large $m$ and $n$ and dont now how to overcome it. ...
55 views

### How to Find the Probability of a Distribution based on another Distribution. [closed]

The question is : Suppose we first sample $X \sim N(0, 1)$ and then sample $Y \sim N(X, 1)$. What is the probability that $P(Y \leq 2)$? I know how to sample the $X$ distribution, but I'm not sure how ...
99 views

### Is there a compiler for every Turing-complete programming language that compiles this programming language into any other programming language?

Recently I had to prove some theorems about programming languages. Originally I thought that I could assume that for every programming language there is a compiler that compiles that language into ...
71 views

### Matrices over $\{0,1\}$ equipped with AND and OR

Consider $S = \{0, 1\}$ equipped with the binary operations AND (represented by multiplication) and OR (represented by addition). Is there a name for this algebraic structure? Given that AND and OR ...
47 views

### How does this fit in with the definition of finite boolean functions?

My lecture defined that a boolean function is a function f: ${\{0,1\}}^{V} → \{0,1\}$ with $V$ being the set of variables. Moreover a boolean function f: ${\{0,1\}}^{V} → \{0,1\}$ is finite if set of ...
1 vote
37 views

### On the Kolmogorov complexity of integers with large prime factors

Any sufficiently large prime must be compressible, in the sense that $K(p)<\log_2{p}$ for any prime $p$ greater than some constant. It seems it is also implied that given any $d$, you can choose a ...
61 views

### No Turing machine can detect whether another Turing machine will halt in all cases. But exactly how well can one do?

The undecidability of the halting problem implies that no Turing machine can determine whether an arbitrary Turing machine passed to it will halt or not on a given input. However, we can devise ...
1 vote
95 views

### Finding the Fastest Algorithm for Dividing Metal Bars and Proving its Efficiency

Dappy is given a metal bar of length a. He can divide a metal bar at any point into two smaller metal bars, such that their lengths sum up to the original length. This process takes some time though, ... 15 views

### How to prove the relation involving difference between value functions of two different policies and the sum of advantage function over time?

In reinforcement learning, how do you prove the following relation between the difference in value functions of two policies? The value function $V^\pi(s)$ represents the expected cumulative reward ...
1 vote
57 views

### Is the three dimensions Navier-Stokes equations problem a P problem?

Edited. If we define this problem by a yes/no question, like: « Does the 3D Navier-Stokes equations problem have a positive solution (which means that there are respecting problem conditions solutions ...
1 vote
51 views

### Exptime problems not known to be in np class [closed]

since its an open problem if NP = EXP, so i want to know the problems in exp for whom no polynomial certificates for output verification have been found so far . Any link or name would be nice
32 views

### Does My Conjecture on Selecting 'Special Nodes' in TSP Matrices to Eliminate 97-99% of Edges Hold Potential for Polynomial Time Solutions? [closed]

I was wondering something, let's say in a symmetric distance matrix of a sample of TSP, there was a sure algorithm that could remove around 97% of the values (weights or distances) that wouldn't ...
25 views

### Converting a 2-adic expansion to a fraction

I've been experimenting with the idea of using 2-adic expansions of numbers to efficiently do division on computers. For instance, if you have the 8-bit integer, 171(0b10101011), multiplied by 3 ...
1 vote
28 views

### How to find values that generate a particular boolean expression

On question 1 of our homework we are asked to find which values of the boolean variables equate to the resulting boolean expression. I tried finding resources on how to complete this but I came up ...
15 views

### Numerically robust mechanism to find a basis for the null space?

Say you are in $\mathbb{R^3}$ and are given a set of directions that is contained in some plane. The span is, by definition, isomorphic to $\mathbb{R^2}$ and thus the null basis is given by a single ...
142 views

### Is there any mathematical operation that can be reversed to two unique numbers?

Is there any mathematical operation “op”, such that when applied to two integers a, b: a op b = n. We can use that n and reverse the operation, to get n = a op b? For example, the sum is not ...
1 vote
48 views

### Is a proof one kind of computation?

Is proving mathematical theorems one kind of computing? I read somewhere in a book that proofs are one kind of computation. I am not talking about formal proofs, I am talking about the informal ...
65 views

52 views

### Turning division by zero to zero with basic math operators

I need to compute $\frac{const}{y}$, where $y$ may equal $0$ to present PC state in a human-readable format from exposed internal registers. Is it possible to build an expression of basic math ...
48 views

### How to compute the successor to a given floating point number

Let $F$ the set of all floating point number $n2^e$ such that $-2^{53} < n < 2^{53}$ and $−1074 \leq e \leq 970$. Let $F^* = F - \{\max(F)\}$ I assume $F$ not to be dense, and therefore there ...
40 views

### $y = x (a - x) (x - 1)$ how to efficiently compute $y$ and $x^3$ efficiently?

specifically i'm giving this operation $x(a - x) (x - 1)$ a bunch of times the GPU to compute as part of a bigger project. considering a low precision 16 bit maybe 32 bit ($n \log(n)$ does not take ...
1 vote
81 views

### Algorithm for finding a Hamiltonian path in a DAG

Consider a directed acyclic graph (DAG) $G$ with $n$ vertices that does not possess a Hamiltonian path. Which algorithm can be employed to determine the minimum number of additional edges required to ...
64 views

### Best approximation of ellipse for collision detection.

I'm working on a personal JavaFX project, and I need to check if two sprites overlap. Originally, I modelled them as ellipses. I was then able to then simplify the problem into checking the ...
1 vote
113 views

### is the normal proof of halting problem undecidability is wrong?

The normal proof goes as follows: if H(f) is a program that takes the source code of any program f and return whether it halts, we define G to be if(H(G)){ loop forever } else { halt } Which is a ...
71 views

### Is there an algorithm for this variant of the dominating set problem?

I stumbled upon this interesting variant of the dominating set problem lately, and as I have not been able to find a consecrated name, I suppose it has not been thoroughly studied yet. The formulation ...
240 views

### Need an intuitive example for how "P is necessary for Q" means "Q$\implies$P"?

I am confused about how "P is necessary for Q" means "Q$\implies$P" (source: Kenneth Rosen DMGT). Intuitively, I interpret "P is necessary for Q" as "for Q to happen,...
### CFG for $L = \{w_1w_2 \cdots w_{2n} \mid n > 0, w_i \in \{a, b\}, 1 \leq i \leq 2n, w_j = b, w_{n + j} = a \ \exists j, 1 \leq j \leq n\}$
I think this is somehow related to the language describing all strings not of the form $ww, w \in \{a, b\}^*$, but I am still not quite sure how. Of course, I have done some thinking and it is evident ...