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
3
votes
1
answer
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 ...
- 33
1
vote
0
answers
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 ...
- 25.6k
0
votes
0
answers
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:
...
- 57
0
votes
0
answers
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?
- 11
2
votes
0
answers
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 ...
- 2,464
0
votes
0
answers
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 ...
- 882
1
vote
1
answer
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\}$, ...
- 3,042
9
votes
1
answer
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 ...
- 177
1
vote
2
answers
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 ...
- 71
1
vote
0
answers
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. ...
0
votes
1
answer
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 ...
- 9
3
votes
0
answers
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 ...
- 31
2
votes
2
answers
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 ...
- 65
0
votes
1
answer
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
1
answer
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 ...
- 5,739
2
votes
1
answer
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 ...
- 426
1
vote
2
answers
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, ...
user1251760
0
votes
0
answers
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
1
vote
0
answers
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 ...
- 63
1
vote
0
answers
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
- 89
0
votes
1
answer
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 ...
0
votes
0
answers
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
0
answers
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 ...
- 11
0
votes
0
answers
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 ...
- 3,250
0
votes
4
answers
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
0
answers
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 ...
- 19.2k
0
votes
1
answer
65
views
Give a lower bound of $T$ if $\log T / T \leq \epsilon^{2}$
Let $T>10$. Give a tighter lower bound of $T$ if $\log T / T \leq \epsilon^{2}$.
I know that $T$ should be in the order of $\widetilde{O}(\epsilon^{-2})$. How can we prove this?
Suppose $T = A \...
- 195
1
vote
0
answers
69
views
Is there any time constructible function $f$ such that $f(n) = o(n\lg n)$ ？
In Sipser's Introduction to the Theory of Computation, the definition of time-constructible function is,
a funciton $f:\mathbb{N}\to \mathbb{N}$, where $f(n)$ is at least $O(n\lg n)$, is called time ...
- 11
0
votes
0
answers
48
views
How is $f_1(n)$ not computable but $f_2(n)$ is?
I came across these two introductory examples on the topic of computable.
$$f_1(n) = \begin{array}{cc}
\Bigg \{ &
\begin{array}{cc}
1 & ,\text{if n appears in the decimal ...
- 23
0
votes
1
answer
89
views
Natural deduction with $(A→B)→C, A∧B ⊢C$
$(A → B) → C, A ∧ B \vdash C$
1.$\hspace{1cm}(A → B) → C \hspace{1cm}$premise
2.$\hspace{1cm}A ∧ B \hspace{2.5cm}$ premise
$\hspace{2cm}$ 3. $\hspace{1cm} A \to B \hspace{1cm}$ Assumption
$\hspace{2cm}...
- 1,015
0
votes
0
answers
61
views
Is this natural deduction proof of $\exists x \neg Px \vdash \neg \forall x Px$ correct?
When it comes to proofs there is no way to tell whether I have done correct or not. In the solution they did in another way which makes me wonder if this correct? For future question, how can I verify ...
- 1,015
4
votes
1
answer
122
views
finding the radius of a cylinder based on camera position
Not entirely sure this is the right forum, but I'll give it a go.
I have a cylinder that is projected onto a 2d plane (3d world with a virtual camera).
What I want to figure out is, given a point on ...
- 181
1
vote
1
answer
38
views
Provide an interpretation where a formula $\forall x \exists y G(x,y) \wedge \neg \exists z G(z,z)$ of predicate logic holds true
Provide an interpretation where $∀_{x}∃_{y}G(x,y) ∧ ¬∃_{z}G(z,z)$ holds.
G(x, y) = x "greater than" y
This gives us the meaning that for all numbers, there exists a number where x is ...
- 1,015
0
votes
0
answers
28
views
How can we define the error of the CORDIC Algorithm for calculating sin(x) as a function of the number of iterations/rotations performed?
I intend on comparing the CORDIC algorithm and the Taylor Series expansion for computing sin(x). However, I need to compare them on the basis of accuracy and time complexity.
How can we determine the ...
- 11
1
vote
0
answers
47
views
Claim that the class of context-free languages is closed under $f$ [closed]
Given an alphabet $\Sigma$, consider the operation $f : \Sigma^* → \Sigma^*$, defined as
$$
f(w) = w_n \circ w_{n−1} \circ w_{n−2} \circ \cdots \circ w_1,
$$
where $w = w_1 \circ w_2 \circ w_3 \circ \...
1
vote
2
answers
139
views
How do I find the infinite sum of $\arctan(2^{-n})$?
I am looking at the CORDIC Algorithm and I want to show that iterative rotations by the nth angle given by arctan $2^{-n}$ is greater than $\frac{\pi}{2}$.
$$
\sum_{n=0}^{\infty} \arctan 2^{-n}
$$
- 11
1
vote
1
answer
212
views
Complexity of a list problem
I have two lists $L_1$ and $L_2$ of real numbers which are of equal length $n$ and I would like to analyze the complexity of the following problem:
Select an index set $I\subseteq \{1,...,n\}$ with ...
- 19
5
votes
1
answer
128
views
What are the chances that the Enemy/Defender game has a stable solution?
There is a game called Enemy/Defender that you might play with kids. The setup is as follows:
Everyone stands in a circle. You say, "Look around the circle and select someone (at random) to be ...
0
votes
2
answers
130
views
How to prove with natural deduction?
Given this question, I tried solving in the first picture as you can see, but I didn't know how to continue and the second image is the right way to solve it. My question is have I done right so far? ...
- 1,015
0
votes
0
answers
51
views
Propositional logic: Natural deduction
Is the first solution valid? If not, can someone explain to me why the first solution is not valid but the second one is? Both claim that p and not p is true though?
$\lnot p \to p \vdash p$
$1 \...
- 1,015
0
votes
1
answer
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 ...
- 133
0
votes
1
answer
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 ...
- 57
0
votes
0
answers
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
1
answer
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 ...
- 1,988
0
votes
1
answer
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
0
answers
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 ...
2
votes
1
answer
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 ...
- 21
5
votes
5
answers
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,...
- 59
0
votes
0
answers
56
views
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 ...
- 127
0
votes
1
answer
59
views
Why does adding 1 when converting to and from Two's Complement work?
I understand the steps for converting to and from two's complement. Represent the number as a positive base binary value, flip the bits, add 1. I don't understand why adding the 1 actually works ...
- 47