Tagged Questions
0
votes
0answers
12 views
Time complexity of the described DTM
There is a DTM with alphabet $\Sigma = \{∗, 0, 1\}$, that on input $1^n$ outputs $1^n ∗ 1^n$. That is it takes a string of $n$ ones and replaces it by two strings of $n$ ones, separated by a blank ...
1
vote
1answer
26 views
Are these two context free grammars equivalent?
Let Σ = {a,b}. A CFG for the language {a^nb^m | n > 2m} can be written as:
S-->aaSb
S-->A
A-->aA
A-->a
Would it be equivalent to write this CFG as:
...
1
vote
0answers
28 views
is the $d$-dimensional arrangement of Trees still $NP$-hard?
The $d$ dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...
0
votes
1answer
24 views
How can i bound the largest edge length of an $n$-point metric in $O(n)$?
For a given metric $d$ on a finite (vertex) set $V$, how can I bound the largest edge length in $O(|V|)$? While (wlog) assuming that the smallest edge length is at least $1$.
0
votes
0answers
28 views
Describing a multitape Turing Machine that enumerates the set of $i$ such that $w_i$ is accepted by $M_i$
I am having trouble with this problem. It regards the theory of Turing Machines.
Describe a multitape Turing Machine that enumerates the set of $i$
such that the word $w_i$ is accepted by the ...
6
votes
1answer
52 views
Can the rank of the homology group of an abstract simplicial complex be computed in polynomial time?
I want to write a function that does the following:
Input:
An integer $n$
A function $f$ that maps nonempty subsets of $\{1, \dots, n\}$ to "yes" or "no" such that (a) every singleton set gets ...
1
vote
1answer
50 views
how discrete mathematics is related to computerscience
I have this basic question for sometime since i came across discrete mathematics, hence this question. How discrete mathematics is related to computer science. How its notions are used in the field of ...
2
votes
2answers
45 views
Question about what it means to be in “NP”
Suppose I am trying to prove language $L$ is in NP. Does it suffice to construct a nondeterministic Turing machine that accepts all strings in the language in polynomial time? Or must the machine ...
7
votes
3answers
132 views
Why isn't NP = coNP?
Suppose a language L is in NP. I think that means a nondeterministic Turing machine M can decide it in polynomial time. But then shouldn't it be in co-NP, because can't we define a new Turing machine ...
0
votes
1answer
47 views
Proving By reduction from the Halting Problem
I want to solve the following exercise in Computability and Complexity Theory:
By providing a reduction from the HALTING problem to REACHABLE-CODE,
prove that REACHABLE-CODE is undecidable.
...
0
votes
0answers
15 views
What is the computational complexity of END-OF-THE-LINE when we require the output node to be connected to the input node?
The problem END-OF-THE-LINE is:
Let $G$ be a directed graph such that each node has in- and out-degree at most $1$. Given a node $g$ of $G$, either (1) decide that $g$ is a balanced node, or (2) ...
1
vote
1answer
33 views
Big $\mathcal{O}$ notation for multiple parameters?
The following is an excerpt from CLRS:
$\mathcal{O}(g(n,m)) = \{ f(n,m): \text{there exist positive constants }c, n_0,\text{ and } m_0\text{ such that }0 \le f(n,m) \le cg(n,m)\text{ for all }n ...
1
vote
2answers
48 views
Confusion related to P and NP problems
I have this confusion related to P and NP problems. Why is P a subset of NP? I didn't get it. P problems can be solved in polynomial time. However, NP problems cannot but only verify if a solution is ...
0
votes
1answer
78 views
Array resize problem
I need help with this problem if anyone can help.
Suppose you have an empty array of size $s$. Then you keep inserting elements in it. But before you insert an element, if the array is filled, then ...
0
votes
1answer
20 views
Resizing array problem
I need some help with this problem.
Suppose you have an array of size $n$ where $n = 4^i$ for some $i \geq 0$, with initially $n$ elements in it. Let $m$ be the current number of elements in the ...
