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

2
votes
1answer
316 views

what is the relationship between the complexity class E(and EXP) and NP?

I want to know any relationship between the complexity class E(and EXP) and NP. I also would like to know whether there is any $DTIME$ formulation or relations of $NTIME(O(n^k))$ where n is the size ...
1
vote
2answers
54 views

Proof regarding notations

I tried to solve the following question: Let $f,g$ be non-negative functions such that $f(n)=g(n)\left[1+o(1)\right]$. Prove that $f(n)=\Theta(g(n))$. I looked on two cases: ...
2
votes
3answers
24 views

Finding a ratio from a set of discrete values

For x = p/q, where x is a known value between 0.000 and 1.000 rounded to the thousandths place, p is an integer value between 0 and 127, and q is an integer value between 0 and 255: what is p and q? ...
1
vote
3answers
26 views

Is there a 5-regular graph of order 7?

How can I decide if there is a 5-regular graph of order 7? Some hints or tips would be appreciated. This question arises in studying for a graph theory course.
1
vote
1answer
32 views

The traveling salesman problem is NP-complete Reduction

The traveling salesman problem is NP-complete. Proof: First, we have to prove that TSP belongs to NP. If we want to check a tour for credibility, we check that the tour contains each vertex once. Then ...
2
votes
2answers
104 views

Knapsack problem NP-complete

Show that the knapsack problem (Given a sequence of integers $S=i_1, i_2, \dots , i_n$ and an integer $k$, is there a subsequence of $S$ that sums to exactly $k$?) is NP-complete. Hint:Use the exact ...
2
votes
1answer
31 views

What is a simple proof that something is np complete that does not use np completeness of something else?

What is a simple proof that something is NP complete that does not use NP completeness of something else? Every proof seems to reduce to something else being NP complete.
1
vote
0answers
53 views

Traveling salesman neighborhood

I am solving some TSP problems and i got this one and i am not pretty sure about my answer. By seeing TSP as a formal combinatorial problem, i have that the Feasible solutions $F$ is the set defined ...
0
votes
0answers
36 views

Interstellar's Gargantua (Black Hole) Equation [on hold]

I don't really know if this is a physics, computer science or mathematics question so kindly excuse me if I posted it at the wrong place. I want to know what was maths/equations that were used to ...
2
votes
3answers
94 views

A mathematically mature introduction to Turing Machines and Computability [reference-request]

In the computer science course for mathematicians held at my university Turing Machines have been presented very briefly. So much so that I didn't quite get why they are relevant to mathematics. I did ...
0
votes
1answer
39 views

Quicksort-How did we get the relation?

At the proof of the theorem that the expected time of Quicksort is $O(n \log n)$, there is the following sentence: We suppose that the partitions are equally likely, so the possibility that the sizes ...
1
vote
1answer
53 views

Expected time of Quicksort

I am reading the proof of the theorem: The Algorithm Quicksort sorts a sequence of $n$ elements in $O(n \log n)$ expected time. The proof is this: For simplicity in the timing analysis assume ...
3
votes
1answer
26 views

Number of edges in a graph with n vertices and k connected components

Let $m$ be te number of edges, $n$ the number of vertices and $k$ the number of connected components of a graph G. Prove that: $m$ $\leq$ $\frac{(n-k+1)*(n-k)}{2}$ Thanks!
0
votes
1answer
31 views

Existence of a maximum matching containing a vertex $v$ in a graph

Let $v$ be a vertex of a graph $G$, which is not isolated. Prove the existence of a maximum matching in which $v$ is saturated (matched).
1
vote
0answers
19 views

The optimization problem of soft margin Support Vector Machine: How to interpret?

I try to understand what exactly we are trying to optimize in the case of Support Vector Machine problem, which supports soft margins. The original problem is posed first as, without soft margins ...
1
vote
1answer
283 views

Finite state machine

I am doing discrete math, and we are studying Finite State Machines. But i am a little confuse on how to do this. Here is a question, Write a regular expression for the language, and define a finite ...
-1
votes
0answers
23 views

Algorithm for vector space transformation [on hold]

In my text book I've got an example which is as follows: Create an algorithm which calculates coordinates of a point after a space transformation took place. Transformations may be scaling or ...
0
votes
1answer
13 views

Tree Traversal-Is the order ascending?

I have a question about the traversal of a tree. When we print the values of a binary search tree using in order traversal are the values printed in an ascending order??
1
vote
1answer
459 views

Using BFS or DFS to determine the connectivity in a non connected graph?

How can i design an algorithm using BFS or DFS algorithms in order to determine the connected components of a non connected graph, the algorithm must be able to denote the set of vertices of each ...
16
votes
4answers
2k views

Is chess Turing-complete?

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff ...
4
votes
2answers
425 views

An “uncountable” Turing Machine?

A proof of the insolubility of the halting problem is a diagonalization, which I'm sure most of you have seen. I am not very familiar with set theory, but it strikes me as similar to Cantor's proof of ...
0
votes
0answers
14 views

Interpolating transformation matrices

I read not to interpolate transformation matrices by linearly interpolating. Can someone explain to me why interpolating transformation matrices by linearly interpolating the matrix components is a ...
2
votes
1answer
53 views

What format is this?

I was given a snippet and can't seem to parse it myself, what's the name of this format and is there a tool that will render it like latex or mathML like this site does? ...
0
votes
0answers
47 views

What is the highest number that could be written down in principle using all computers in the world?

I read somewhere in the internet, that the capacity of all computers in the world would be about $10^{18}$ bytes. Does this mean, that in principle, a number with $10^{18}$ digits could be written ...
2
votes
0answers
40 views

How can we find the elements?

I want to describe an algorithm with time complexity $O(m)$ that, given a set $M$ with $m$ numbers and a positive integer $p \leq m$, returns the $p$ closest numbers to the median element of the set ...
1
vote
1answer
54 views

How does the function work? [closed]

Could you explain me the function of the following two algorithms? ...
0
votes
1answer
19 views

A language $L$ is polynomially transformable to $L_0$

Could someone explain to me the following definition?? A language $L$ is polynomially transformable to $L_0$ if there is a deterministic polynomial-time-bounded Turing machine $M$ which will convert ...
1
vote
2answers
445 views

Check Whether A Boolean Formula Has One Satisfying Assignment

So I'm reviewing old homeworks for an upcoming comp sci test and I came across this question: Say whether the following statement is True, False or Unknown: The problem of checking whether a ...
0
votes
3answers
52 views

How to find upper and lower bound without using formula?

I am studying discrete math for tomorrow's exam and got stuck in the below question. I tried to google it and couldn't find anything usefull. Prove the following sum is theta(n^2) (we have to find ...
-5
votes
4answers
58 views

How many possible 1mb files are there? [closed]

If you look at all combinations of data that can be stored in a 1mb file, how many are there before you have every possible 1mb file? How much space does that take up?
4
votes
3answers
7k 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 ...
0
votes
1answer
106 views

Applications of Concrete Categories in Computer Science

From Wiki: "In mathematics, a concrete category is a category that is equipped with a faithful functor to the category of sets. This functor makes it possible to think of the objects of the category ...
1
vote
1answer
12 views

Prove that $L=\{a^nb^nc^md^m \mid m,n >=0\}$ is context free language

I'm trying to write the grammar of this language, in order to prove that it is CFL but I'm stuck because m or n could be 0. The language is: $L=\{a^nb^nc^md^m \mid m,n >=0\}$ . If they were ...
0
votes
0answers
33 views

AoPS Intermediate Algebra vs. Higher Algebra by Hall and Knight? And some more questions about learning math.

Ok. I'm learning algebra at the level of AoPS algebra 2, and I want to quickly progress through math. Allow me to explain the situation. I am highly interested in artificial intelligence/computer ...
0
votes
0answers
30 views

Show that it is NP-complete [closed]

Show that the problem of determining whether a regular expression over the alphabet $\{0\}$ does not denote $0^*$ is NP-complete. Could you give me some hints how I could do that??
3
votes
1answer
99 views

What kind of edge do we have?

In order to find the kind of the edges of a graph, at which we applied the Depth-first search algorithm, we could use this: $$\begin{bmatrix} \text{ tree edges: } x \to y & [d[y],f[y]] \subset ...
1
vote
0answers
34 views

Turing Machine That Accepts Machines With Undecidable Languages

So I'm reviewing my Computability notes for my final, and I understand how reduction arguments work, but I'm having trouble framing one for the following Turing machine: Undecidable TM = { ⟨M⟩ | L(M) ...
1
vote
1answer
22 views

Why the only binary MDS codes are trivial ones?

Why the only binary MDS codes are trivial ones? I have been thinking how to draw a contradiction by assuming the MDS code is not trivial. Thank you very much!
2
votes
2answers
17 views

Proving that median of list $[x_1,x_2,…,x_n]$ minimises the sum $\sum_{i=1}^{i=n} |x_i-m|$ where $m$ is some number

The problem is in the title. Here is a detailed description: Let's say we have list $[x_i]_{i=1}^{i=n}$ where $x_i\in\Bbb{N}$. I want to pick such $m\in\Bbb{N}$ which minimises the sum ...
4
votes
1answer
81 views

Minimizing the distance between points in two sets

Given two sets $A, B\subset \mathbb{N}^2$, each with finite cardinality, what's the most efficient algorithm to compute $\min_{u\in A, v\in B}d(u, v)$ where $d(u,v)$ is the (Euclidean) distance ...
0
votes
1answer
107 views

Boolean algebra - cube - minimal disjunctive normal form

I have a test coming up and I would like to know how to solve these kinds of problems. This is the description: ...
1
vote
1answer
49 views

Trying to find formula for max number of nodes in a non-Binary tree.

I'm trying to find the max number of nodes in a tree that is defined as follows: The root can have at most $2$ children. Each subtree on the left can have at most $L$ children. Each subtree on the ...
0
votes
0answers
20 views

Is there a universal constant for size of disjoint clauses in 3-CNF

We are given a 3-CNF formula $\Phi$ on n variables, and a guarantee that at least 1% of $2^n$ possible assignments satisfy all clauses in $\Phi$. Now construct set $S$ of disjoint clauses so that no ...
3
votes
3answers
71 views

Can a Turing Machine process an infinite string?

I read in a text book once that a finite state acceptor machine cannot be an acceptor for an infinite language. My question is does this apply to Turing Machines? The implication, it seems to me, ...
2
votes
0answers
29 views

Linear Algebra Book Recommendation [duplicate]

I am taking an undergraduate course in computer science an is in the first year of my college. I like mathematics and am willing to learn Linear Algebra first and then move on to Abstract Algebra and ...
1
vote
1answer
40 views

How do I solve for the zeros of a Chebyshev polynomical? (on a computer)

I am working on a computer program and have a method that returns a number for a given $x$, $y$. So $f(x, y) = z$, where $f$ is my method. if I know $y$ and $z$, can I find what $x$ will be, without ...
3
votes
2answers
121 views

Application of Mergesort

We have $8$ players and we want to sort them in $24$ hours. There is one stadium. Each game lasts one hour. In how many hours can we sort them?? I thought that we could it as followed: ...
1
vote
1answer
21 views

Discreet Math - Given n>= 5 how many times does fib(4) occur?

I have been trying to solve the below problem (and similar problems) but I have no clue how to tackle it. Can please help me tackle this particular problem, and how to attack similar problems? The ...
1
vote
1answer
15 views

Urn Probability Combination Problem

I am in my first year of Comp Sci and I am reviewing for my Math Final. There are two Urns $U_1$ and $U_2$. $U_1$ has $10$ red balls and $8$ blue balls. $U_2$ has $16$ red and $4$ blue. Suppose you ...
0
votes
0answers
18 views

What does it mean for an equivalence class to straddle a set of states?

In the following question, what does it mean for an equivalence class to straddle a set of states? Assume you currently have two equivalence classes Φ and Ψ. In addition you have a set of ...