Tagged Questions
2
votes
1answer
27 views
Books on computational complexity
Can anyone recommend a good book on the subjects of computability and computational complexity? What are the de facto standard texts (say, for graduate students) in this area?
I've heard a thing or ...
1
vote
1answer
33 views
2-colorable belongs to $\mathsf P$
To show that 2-colorable belongs to $\mathsf P$, I have a straightforward mental description in mind that I don't think will be considered as a formal proof. Hence I am interested to know how this ...
0
votes
0answers
16 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
29 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
54 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 ...
0
votes
0answers
38 views
Potential function in amortized analysis
I am trying to calculate the amortized cost of a dynamic array, that's size becomes 4 times the size when the array is filled. (when you re-size, you create a new one and copy the elements there).
...
2
votes
1answer
42 views
How is naive CLIQUE algorithm polynomial time?
I am reading Introduction to Algorithms 3rd for my CS course. Just before theorem 34.11 on pg 1087, it says the running time of the naive algorithm to try all k-subsets of $V$ is ...
0
votes
1answer
79 views
Decimal expansion in logic Church thesis
How can we show that the function $n \mapsto e_n$, where $e_n$ is the $n$-th digit in the decimal expansion of $e$, is computable?
I have some idea in terms of Cantor's diag. argument, but I need to ...
0
votes
0answers
41 views
Maximum Independent Set by Distributed Algorithm
Maximum independent set on the ring could be found by distributed algorithm like following (unique UID's is required).
...
1
vote
2answers
86 views
Determining function for recursive Fibonacci algorithm
I'm given a function:
int fib(int n) {
if (n == 0 || n == 1) return n;
return fib(n - 1) + fib(n - 2);
}
from which I am supposed to determine a ...
1
vote
1answer
40 views
How to compute the complexity
1) If $a(n)=O(n^2)$ and $b(n)=O(n^3)$. Can someone tell me how to compute the computational complexity of
$$ c(n)=\sum_{k=1}^{n}a(k)b(k) $$
What rules apply?
I think it might be $O(n^6)$, but this ...
2
votes
1answer
46 views
A way to codify (pre-calculatate) if a one Tree Node is a descendant of another
I have a simple, 1-directional tree representing the veins in a human body. It looks somewhat like this (red dots are nodes, blood flow is always downwards, sorry for my drawing):
What I need is a ...
0
votes
1answer
178 views
How to prove perm-power is in P?
Let $\mathit{PERM\text{-}POWER} = \{ \langle p, q, t\rangle \mid p = q^t \}$ where $p$ and $q$ are permutations on $\{1, \ldots, k\}$ and $t$ is a binary integer. How do I prove that ...
1
vote
2answers
54 views
What is this number $k$?
I'm reading A first Course on Logic, (Hedman).
An algorithm is said to be polynomial-time if there is some number
$k$ so that, given any input of size n, the algorithm reaches it's
conclusion ...
1
vote
1answer
87 views
Polynomial complexity algorithm of partition problem with sets of equal size
Partition problem is well known ( http://en.wikipedia.org/wiki/Partition_problem ).
Let's add an additional condition: sizes of both sets should be equal. Is there a pseudo-polynomial solution to ...
2
votes
1answer
110 views
Function problem vs. decision problem
Take the set $FP$ of number-theoretic functions that are computable in polynomial time. Let us restrict to those functions with range in $\{0,1\}$, $FP_{0,1}$. Is there any correspondence with ...
1
vote
2answers
102 views
Algorithmic Complexity of $i^2$
I am new to the Big O notation in regards to algorithm design. I have had some exposure to it but I am not sure how to find the algorithmic complexity of a given function for a summation. If someone ...
0
votes
1answer
145 views
DTIME and time hierarchy theorem
we know that
$\mathrm{DTIME}\left(o\left(\frac{f(n)}{\log(f(n))}\right)\right)$ is a subset of $\mathrm{DTIME}(f(n))$
but what can we say about
$\mathrm{DTIME}{ \left(o\left(\frac{f(n)}{ (\log f(n) ...
2
votes
2answers
104 views
Can weight-restricted versions of monotone 2-SAT be decided in polynomial time?
I'm trying to answer a question from one of past test,
The question is to decide if the following language is $\mathrm{P}$ (can be decided in a polynomial time) or $\mathrm{NPC}$ (can be decided by ...
1
vote
2answers
94 views
How can the following language be determined in polynomial time
I'd love your help with understanding why the following is decidable and can be determinate in polynomial time ($L \in P$).
$L=\{(\langle M \rangle,w)|M$ is a Turing machine with Q states and one ...
0
votes
0answers
125 views
Solving a problem by reduction
I am aware that for a problem to be considered NP-Hard, any problem in NP must be reduceable to your problem (problem which you are trying to prove is NP-Hard).
Let's assume that you have proven that ...
6
votes
2answers
346 views
Two $NP$-complete languages whose union is in $P$?
I've been thinking about transformations on $NP$-complete problems that produce languages known to be in $P$. However, I can't seem to find an example of two $NP$-complete languages whose union is in ...
2
votes
1answer
89 views
A question about sorting
I've always been thought that the fastest way to sort an array of numbers has complexity $O(n \log (n))$. However, radix sort has complexity $O(kn)$ where $k$ is the number of bits. There are even ...
3
votes
1answer
83 views
Determining position at some point in time
I try to solve the following problem.
On $n$ parallel railway tracks $n$ trains are going with constant speeds $v_1$, $v_2$, . . . , $v_n$. At time $t$ = 0 the trains are at positions $k_1$, ...
1
vote
2answers
79 views
non-complete problem collapsing to a lower complexity class complete problem
Let us say that there is a NP problem that is not a complete problem. And let us assume that someone found that the problem is in fact P-complete problem.
Does this imply P=NP?
2
votes
1answer
310 views
Form or asymptotic behaviour of $T(n) =2T(n-1)+n$
$T(n) =$ if $n=1$, then time execution is $1$, if $n \geq 2$ then $2T(n-1)+n$
The options are:
$T(n) = 2^{n+1} - n - 2$
$T(n) = O(n2^n)$
$T(n) = \Omega(n)$
$T(n) = \theta(2^n)$
Thanks.
0
votes
1answer
61 views
Time to resolve a problem of size $1000$ in one second, how time take resolve the same problem of size $10.000$ in $n^2$?
A algorithm require one second to resolve a problem of size $1000$ a local machine.
How long time take the same algorithm to resolve the same problem for a problem size of $10.000$ if the algorithm ...
1
vote
0answers
199 views
Polynomial-Time reduction: Clique Problem
Here is an exercise my friend proposed to me:
Show that the maximum clique problem polynomial time reduces to the maximum independent set problem.
Here is my attempt at solving it:
It is known ...
1
vote
4answers
142 views
A “State Hierarchy” Theorem for Turing Machines?
In complexity theory, there are time hierarchy theorems for Turing machines that show that for certain functions $f$, there exist problems that cannot be solved by a Turing machine in $o(f(n))$ time.
...
0
votes
0answers
31 views
Function for Block Sensitivity comparison with Sensitivity
I need to find function $f$ where Block Sensitivity is larger than its Sensitivity
$bs(f) > s(f)$
For example sortedness function where: $0000$,$0001$,$0011$, $0111$, $1111$, $1110$, $1100$, ...
1
vote
1answer
65 views
Finding the computational complexity of an algorithm
Algorithm:
for (int i = 0; i < 2*n; i += 2)
for (int j = n; j >i; j--)
foo();
I want to find the number of times foo() is called.
...
0
votes
1answer
179 views
symmetric difference of languages - both are in NP and coNP
I have this problem,
Let $L_1,L_2$ be languages in $NP \cap co-NP$. I want to show that their symmetric difference is also in $NP \cap co-NP$. Like:
$L_1 \oplus L_2 = \{x | x$ is in exactly one of ...
0
votes
1answer
296 views
What is the computational complexity of a brute force perfect numbers finder algorithm?
A loop goes thru all numbers from one to N to find perfect numbers. For each number in the range, it checks all numbers less than it to see if it's a divisor by modding it by the number and checking ...
2
votes
2answers
159 views
Knapsack with non-trivial “utility” function
The standard knapsack problem imagines a thief trying to stick the most items in his knapsack as possible. It assumes that having, say, two Picasso paintings is twice as good as having one.
We might ...
2
votes
0answers
120 views
2-Player Game PSpace-Completeness
So there is a n x n game board and each location on the board has an integer. Player one picks a number from row 1 and player 2 picks a number from row 2 and they alternate until there are no more ...
0
votes
1answer
225 views
NP-Completeness of Certain Bounded Degree Graphs
I was studying time complexity when it comes to bounded degree graph problems and I was wondering if I can get help with the following two problems.
1) L = set of all (G, k) where G is a graph with ...
1
vote
2answers
348 views
P or NP-Complete? (concerning 2-CNF formulas)
I have two languages that I want to either prove is in P or NP-complete.
1) 2-CNF formulas where there exists an assignment that satisfies the 3/4 of the first 1000 clauses and all of the rest.
2) ...
0
votes
1answer
63 views
How do I estimate the time taken? (Growth Rates)
Suppose you have a program that solves an AI problem. When the problem size is $N = 1,000$ your program takes 10 seconds to find a solution. Estimate the time it will take to solve a problem of size ...
