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

0
votes
0answers
12 views

3CNF is not satisfiable iff CNF is UNQ

I'm trying to come up with a reduction to show that $NOT3SAT \leq_p UNQ$, where NOT3SAT is the non-satisfiability problem for 3CNF and UNQ is unique satisfying assignment for CNF. So, what I'm ...
0
votes
1answer
29 views

Number of fragments into which a fixed triangle is cut in the 3d version of the binary space partitioning algorithm

You can scroll down the question, if you're familiar with the construction of a 3d binary space partition as presented in the book Computational Geometry: Algorithms and Applications by Mark de Berg ...
1
vote
1answer
22 views

Why is no analysis possible for the 3d version of the random binary space partioning algorithm?

Let $S$ be a set of $n$ non-overlapping line segments in the plane $\ell(s)$ be the line which contains $s\in S$ $\ell^+$ and $\ell^-$ be the half-plane above and below of a line $\ell$, ...
0
votes
0answers
13 views

Why FFT algorithm (Cooley-Tukey) takes O(nlogn)?

I was wondering how this algorithm can be formally interpreted with an upper bound n*log(n). There's some formal proof for this? I would appreciate if somebody can help me. Thank you.
1
vote
1answer
17 views

Complement of automata

I know that in order for the complement of the automaton to work, it needs to be deterministic and complete, and if it is not deterministic we can always apply the power set construction, and if is ...
1
vote
1answer
29 views

How to prove that a depth-first algorithm labels every vertex of G?

I understand exactly how a depth-first search/algorithm works. You start at the root, and then go to the left most node, and go down as far as you can until you hit a leaf, and then start going back ...
0
votes
0answers
19 views

Progressive simple computation using a number to represent memory

Is it possible to represent computation using a base formula (function) and store it's progressive memory, bit arrays stored as a series of numbers along a $y=c(x)$ style? Where $c(x)$ is a ...
0
votes
0answers
34 views

Prove that for every function $s:\mathbb N\to \mathbb N$ with the following constraints holds that:

Hello guys I'm studying Computational Complexity and I have stumbled upon the following question which I has no idea how to even start proving. I would appreciate any help. Prove that for every ...
0
votes
1answer
50 views

Find the Theta class for the recursion $T(n) = T(3n/4) + T(n/6) + 5n$

$\displaystyle T(n) = T\left(3n\over4\right) + T\left(n\over6\right) + 5n$ is not in the proper form for the Master theorem so I can't really apply it. The only idea I had was changing the ...
0
votes
2answers
45 views

Can I prove that 2n+1 = O(2n)?

Is 2n+1 = O(2n)? In other words, 2n+1 <= c * 2n for any c and all n > n0? I have plugged in numbers but none that worked. Obviously It is also (n) but I am trying to prove the above. Much ...
1
vote
1answer
47 views

Why do at least half of all random orderings generate a binary space partition of size $n+4n\ln n$ in the random binary space partition algorithm?

Let $S$ be a finite ordered set of non-intersecting finite line segments in the plane. Let's randomly shuffle the elements of $S$ such that each possible permutation of those elements has equal ...
0
votes
0answers
41 views

What are the minimum hard constraints that cause the nurse scheduling problem to be NP-complete?

A client wishes to simplify the nurse scheduling problem to 'bypass' the NP-complete nature of this problem. He is hoping to do so by removing the requirement that there are any constraints for any ...
1
vote
1answer
16 views

Cannot create algorithm for decidable language

L2 = {<M> : M is a TM and there exists an input string w such that M halts within 10 steps on input w} Hi. I am creating an algorithm to show above L2 is ...
0
votes
1answer
43 views

Expected number of fragments generated by a random binary space partition (should be plain combinatorics)

Let $S$ be a finite ordered set of non-intersecting finite line segments in the plane. Let's randomly shuffle the elements of $S$ such that each possible permutation of those elements has equal ...
0
votes
1answer
14 views

Higher Order Polynomial Interpolation

I am trying to approximate some log and exp functions in my code. I have implemented linear and cubic splines, but I want more accuracy. I am thinking about biquadratic splines (4th order, quartic), ...
1
vote
1answer
58 views

Closed Form for Sum of Nodes in Binary Tree

Consider a binary tree $T$ with nodes in $\mathbb{Z}^+$, where level $k$ of $T$ contains nodes $2^k$ through $2^{k + 1} - 1$. I have some problems that involve visiting the nodes of $T$ in their ...
0
votes
1answer
37 views

Cannot understand solution (Turing Machine & Reduction)

Photo of my problem that I don't understand About question above in photo, I just can't understand its solution provided. We know the complement of Atm = {...
0
votes
1answer
22 views

How to describe this Context Free Grammar?

I've been having a really difficult time in describing the following Context Free Grammar S → SS | T T → aTb|ab I understand that it must start with an ...
1
vote
3answers
15 views

Help explain this Boolean equation XOR with NOR gates

I'm just starting Boolean algebra and am following an example given in the text that shows the configuration of NOR gates to create an XOR. I cannot follow the algebraic example and would like to have ...
1
vote
2answers
51 views

recurrence algorithms, algebra issues?

So we're given a problem to solve... no other instructions.. the answer is given as well. I am having trouble understanding how this problem is unrolled. I understand that $\sqrt{2^{2^k}}$ can ...
0
votes
2answers
34 views

Finite automata problem

I need to draw a finite automata over the alphabet $\{a,b,c\}$, such that the following properties hold: a word starts with at most two $a$ a $c$ is always followed by an even number of $b$ (0 ...
0
votes
1answer
32 views

Troubles proving $O[f(n)] \cdot O[g(n)] = O[f(n) \cdot g(n)]$

Prove that $O[f(n)] \cdot O[g(n)] = O[f(n) \cdot g(n)]$, knowing that $O[g(n)] = \left\{ f(n) \mid \exists\ c,n_0 > 0\ :\ 0 \leq f(n) \leq c \cdot g(n)\ \forall\ n \geq n_0 \right\}$ I don't ...
-2
votes
1answer
28 views

Importance of Bernoulli Numbers

I'm writing a research paper on the foundations of computing. Supposedly Ada Lovelace wrote an algorithm to find Bernoulli numbers. It sounds cool, but it won't mean anything to my history teacher. ...
0
votes
1answer
18 views

prove this $L$ is not regular?

Consider the language $L=\{a^{n!}\mid n\in\mathbb{N}\}$. I want to prove that $L$ is not regular using the Pumping Lemma. So far i assumed by contradiction that $L\in REG$, so it has a pumping ...
1
vote
0answers
20 views

Ensure exact partitioning when performing masked equality comparison

This question arose from an informatics problem, but I do believe Math SE is the right stack to ask because I am not asking for a algorithm in a specific language but for properties to check using ...
0
votes
3answers
27 views

Complexity analysis of a polynomial and a logarithmic exponential function

I need to find the asymptotic relationship between the functions $f(n) = n^{100}$ and $g(n) = (log_2n)^{(1/2) \cdot log_2n}$. I did the following to show that $f(n) = O(g(n))$: $n^{100} \leq ...
0
votes
1answer
76 views

Encyclopedia of Integer Sequences - Formula

I am trying to reproduce the following sequence (https://oeis.org/A062734): ...
3
votes
0answers
84 views

Reverse Automorphic Numbers

I recently stumbled across Automorphic Numbers (definition and examples). In simple words, a number $n$ is said to be automorphic if last $d(n)$ digits of $n^2$ are $n$ itself (where $d(n)$ is ...
0
votes
1answer
26 views

Correctness of the sweep line algorithm for line segment intersection in the plane

Suppose we are given a finite set $S$ of line segments in the plane and the intersection between two segments is empty or a single point in the interior of both segments at most two segments ...
0
votes
0answers
45 views

Problem with 4-body Matlab code

I'm trying to model the 4 body problem to see how Jupiter, Earth and Mercury orbit the Sun. I found a two body script and adapted it as accordingly to modify my problem, but for some reason the ...
0
votes
1answer
31 views

Create a formula for order of parenthesis

I am stumped at creating a formula (for a coded math problem evaluator) that finds what is within the parenthesis. It gets tricky when you have () within ...
0
votes
1answer
14 views

Proof quadratic congruent equation has no solutions in $\mathbb{N}$

In computer science, quadratic probing is used in hash tables. We choose a $c_1$ and $c_2$ in the hash formula $h(k,i) = (h'(k) + c_1 i + c_2 i^2) \mod{m}$ where $h'(k) = k \mod{m}$ and $m$ is the ...
0
votes
1answer
27 views

Extract each digit of a binary \ decimal number

How can one extract the digits of a binary \ decimal number. For example i have 100110111 to need to extract them only using +,-,*,/ and MOD. I can only use this LOOP Language. Most of the algorithms ...
0
votes
1answer
27 views

What's the difference between “worst/best case big-O()” and omega()/theta()?

In formal discrete math and computer science we talk about "big-θ," "big-O," and "big-Ω" notation, being tight, upper, and lower bounds (respectively) on the growth of properties of an algorithm as ...
0
votes
3answers
37 views

is a^(m)b^(n) | m >= 99 and n>=999 a regular language?

I've been stuck on this problem for a while. Say we have the following language? a^(m)b^(n) | m >= 99 and n>=999 I'm trying to use the pumping lemma to ...
0
votes
1answer
17 views

Proof of Rows/Columns/Main Diagonals in a normal Magic Square

Someone else had asked this question but not to enough detail. I understand that you can sum all of the elements from $1$ to $n^2$ that are in the matrix to get $n^2(n^2+1)/2$. Then from there you ...
1
vote
1answer
45 views

Solving a recurrence with 2 recurrences

I am trying to solve the following recurrence: $$T(n) = T\Big(\frac{n}{3}\Big) + T\Big(\frac{2n}{3}\Big) + O(n)$$ I do not want to use the Akra-Bazzi method nor draw out a recurrence tree. I do know ...
2
votes
1answer
23 views

Space-Hierarchy Theorem in Theoretical CS

Sipser has a proof this theorem that goes like this: $$D = \text{"On input } w$$ $$1. \text{Let } n \text{ be the length of } w$$ $$2. \text{Compute } f(n) \\ \text{using space constructibility and ...
2
votes
0answers
41 views

How to choose set in Group Isomorphism Algorithm( Quasipolynomial time)

In the paper titled "On the $n^{log_2(n)}$ Isomorphism Technique" by Gary L. Miller, it is written A group is a binary operation * , satisfying 1) and 2) . 1) a)$ \exists! x(a*b = x)$ ...
0
votes
1answer
36 views

Proving Gale-Shapley algorithm completes in $O(n^2)$

In Algorithm Design by John Kleinberg and Eva Tardos, the proof for the Gale-Shapley algorithm running in $O(n^2)$ is given In the case of the present algorithm, each iteration consists of some ...
2
votes
0answers
22 views

Math of Repetition

Let R = A (A | B) (A | B | C) (A | B | C | D) ... be an R-Form(A sort of repetition matching grammar). Where A,B,C,D,... are symbols that allow equality comparison. Any sequence of A,B,C,D,... can ...
1
vote
1answer
40 views

Does two's complement arithmetic produce a field isomorphic to $GF(2^{n}$)?

From what I understand, we have these two isomorphisms: $(TC, +)$ is isomorphic to the cyclic group $\mathbb{Z}/2^n\mathbb{Z}$. $(TC, *)$ is isomorphic to the multiplicative group of polynomials. ...
0
votes
4answers
54 views

In formal verification, what is the formal specification, what formally means there?

I have been reading a lot about formal verification of software and apparantly you need to formalize the behaviour of the program to create an equivalent model of it (if I get it right). But nowhere ...
0
votes
2answers
31 views

Practical usefulness of $\mathbb N$ to$\mathbb N\times\mathbb N $or $\mathbb R$ to$\mathbb R\times \mathbb R$ bijection in data processing?

A while ago, I was reflecting on the practical usefulness of bijections from $\mathbb N$ to $\mathbb N\times\mathbb N$, or $\mathbb R$ to$\mathbb R\times\mathbb R$. (We all know they exist.) Wouldn't ...
0
votes
1answer
66 views

How to apply negation to a term?

EDIT: Maybe page 18 of this paper can help. This is a follow up from this question, where I am using ALCQ and I have this: $\lnot(3 \le \exists \text{hasPet}.\text{Animal})$ How to apply the ...
1
vote
0answers
41 views

Determine Huffman Tree Depth Using any combinactory ways?

I see this link for determining depth (height) of Huffman tree, but not useful for me. My Question is: Knowing the frequencies of each symbol, is it possible to determine the maximum height or ...
2
votes
1answer
68 views

Normal Matrix - Is this a valid method of calculation?

Apologies in advance if I have posted unnecessarily. I posted this question on stack overflow but it seems it is more a maths question, hence the re-post here... I have almost finished coding a 3D ...
0
votes
0answers
17 views

Can someone explain the recursive solution to the Josephus Problem?

I saw a quora post that explained it like this: Take a simple case where n=5 and you remove every 3rd person. 1st turn: {1,2,3,4,5} Removed= 3 2nd turn={1,2,4,5} Removed = 1 3rd turn = {2,4,5} ...
0
votes
0answers
41 views

Crank Nicholson Method

I can not figure out what I'm doing wrong in otder to solve this problem using Crank-Nicholson Method. My code is below the picture. ...
0
votes
1answer
46 views

Make individuals distinct

I am trying to construct an ALCQ knowledge base (KB) for some sentences. Here is what I have: Abox (Yiannis is a person and he drinks only one kind of a coffee, frappe): Person(YIANNIS) $\forall$ ...