Computational complexity, a part of theoretical computer science.
0
votes
0answers
14 views
Algorithm for topological sorting without explicit edge list
Suppose I have a set of vertices $V$ and a function $f(V_1, V_2)$ which given two vertices returns +1 if there is an edge from $V_1$ to $V_2$, -1 if there is an edge from $V_2$ to $V_1$, and 0 ...
0
votes
0answers
15 views
Simulating an alternating Turing Machine
I'm trying to figure out this question:
Let's say we have an alternating Turing Machine that makes a restricted number of alternations (i.e. switches from a universal to an existential state or vice ...
1
vote
2answers
114 views
A Problem on Time Complexity of Algorithms
I want no know if the following problem is solved or not, or how can I solve it?
Problem: For every integer $t$, Is there any problem that can be verified in $O(n^{s})$ but its solution can be found ...
1
vote
0answers
19 views
Computational Complexity of the class of $\Delta_0$ functions (over $V_\omega$)
I would like to know where the class of functions whose graph is $\Delta_0$ (over $V_\omega$) fits in the computational complexity hierarchy. Also is there a nice notion of $\Delta_0$-reducibility ...
1
vote
0answers
43 views
Homomorphical Equivalence is NP-complete
Two graphs $G,H$ are homomorphically equivalent if there are exists a homomorphism from $G$ to $H$ and a homomorphism from $H$ to $G$.
The task is to prove that this decision problem ...
42
votes
2answers
816 views
+500
Complexity class of comparison of power towers
Consider the following decision problem: given two lists of positive integers $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_m$ the task is to decide if $a_1^{a_2^{\cdot^{\cdot^{\cdot^{a_n}}}}} < ...
0
votes
1answer
27 views
Proving an equality
Let $f(n) = n^ {\log n}$. Let $p(n)$ and $q(n) \geq n$ be polynomials. I want to show that for
$n$ sufficiently large $f (n)$ satisfies
$$p(n) < f (n) < 2^{q(n)}$$
starting from the above ...
1
vote
1answer
13 views
Notation about a randomized max cut algorithm.
http://users.cms.caltech.edu/~mccoy/publications/teatalk1.pdf
I'm trying to understand the lemma in this.
So we have
Lemma
Let $r$ be a random vector. For any unit vectors $u_{i}$ and $u_{j}$,
...
1
vote
0answers
30 views
Help with Computational complexity of recurrence relation, Big Omega, Big O and Big Theta problem.
The problem that I am struggling with is the recurrance relation
T(n) = floor(T(n/2)) + ceiling(T(n/2)) + ceiling(n/2)
I am supposed to answer true/false to each of the following (along with ...
0
votes
1answer
31 views
Doubts related to set cover NP complete problem
I have some doubts related to the set cover NP complete problem. I am trying to show that a problem is NP complete so I am trying to transform the Set Cover problem to it. However, I have some doubts
...
0
votes
0answers
23 views
Determining if a language is in P or NP?
Is the following language in P or NP?
EMPTY_TM = {⟨N⟩| N is a TM that accepts no input}
Can someone shed some light on how to come to such a conclusion also?
5
votes
1answer
85 views
Simplify $O(n^k/2^n)$
In one of my complexity analysis, I came up with $O(n^k/2^n)$, where $k$ is a fixed number and $n$ is the size of the data. However I rarely see a big-O written as this. Is there a way to even further ...
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:
...
0
votes
2answers
71 views
Determine whether $x^3$ is $O(g(x))$ for certain functions $g(x)$.
a) $g(x) = x^2$
b) $g(x) = x^3$
c) $g(x) = x^2 + x^3$
d) $g(x) = x^2 + x^4$
e) $g(x) = 3^x$
f) $g(x) = (x^3)/2$
Do you guys have any ideas? Thanks!
1
vote
0answers
12 views
Does “short integer solution” lattice problem admit hard instances with q=2?
Let $q$ be a prime, $m,n$ be integers with $m>n$, and $\beta$ be a real number. Moreover, let $A$ be a matrix in $\mathbb Z^{n \times m}_q$. In the "short integer solution" (SIS) lattice problem, ...
4
votes
1answer
245 views
Divisor summatory function for squares
The Divisor summatory function is a function that is a sum over the divisor function.
$$D(x)=\sum_{n\le x} d(n) = 2 \sum_{k=1}^u \lfloor\frac{x}{k}\rfloor - u^2, \;\;\text{with}\; u = \lfloor ...
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 ...
1
vote
0answers
111 views
Is “P vs NP” problem solved?
Many people have tried to solve the very famous problem "P vs NP" and a lot of solutions are proposed. (e.g. A. D. Plotnikov, On the Relationship between Classes P and NP). But I couldn't find any ...
2
votes
1answer
40 views
Confusion related to the definition of NP problems
I have this confusion related to the definition of NP problems. According to wikipedia
Intuitively, NP is the set of all decision problems for which the instances where the answer is "yes" have ...
1
vote
1answer
47 views
How to get the bounds of exponential function
I have this function $(\frac{d}{d+1})^d$. How can I get the lower and upper bound of this function
1
vote
1answer
26 views
Computing the running time of the Fermat primality test
I have a question concerning the Fermat primality test and its running time. According to Wikipedia: "Using fast algorithms for modular exponentiation, the running time of this algorithm is $$O(k ...
3
votes
1answer
33 views
Computational Complexity of Algorithms
I want to know if the following proposition is correct or not?
For any integer k, there exists an problem P for which, the minimum possible time complexity of any solution algorithm is ...
0
votes
1answer
35 views
Looking for a Set generator
English is not my native language.
Hello everybody.
If I have a finite set of natural numbers. It is always possible to find an algorithm that generates it (and of course not the trivial one that ...
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 ...
3
votes
0answers
42 views
How to find an expression whose value is 190
Given a set of numbers (in this case):
3, 7, 7, 100, 50
Either:
prove it is impossible to form the number k = 190 using ( ) + - * / operators between sub set of the these numbers ex: 1000 = ((3 + ...
0
votes
0answers
23 views
Greedy Optimized Subset-Sum Problem
Given positive integers $a_1,...,a_n,b$, find $x_1,...,x_n \in \{0,1\}$ such that $a_1x_1 + ... + a_nx_n \lt b$ but is as large as possible.
How do I show that there is a greedy algorithm to this ...
1
vote
1answer
24 views
Prove that for n~=n' sum is much smaller than the case with n=n'
Hi I want to prove that this summation is much smaller for $n\neq n'$ than for the case where $n=n'$. I have seen this fact with simulation results. But I don't know how to prove it in mathematics.
...
0
votes
0answers
11 views
Holographic algorithms and matchgates
I'm trying to understand holographic algorithms.
http://pages.cs.wisc.edu/~jyc/papers/matchgate-paper.pdf
So I understand how FKT algorithm. However, I don't see how you turn the #P problem into a ...
0
votes
1answer
58 views
what is a closure (hull) operator?
Just that. what is a closure operator?
reading the wiki wasn't enough and i would like to know more.
I'd be happy if someone shared examples of closure operators so that i may further understand ...
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 ...
3
votes
1answer
175 views
Gradualness of Polynomial-time Recognizers
Is there a counterexample or theorem for the question below?
Examples:
Let's look at some examples first to get the feel of it. We'll let $n$ be the length of the input in characters. All the ...
0
votes
0answers
16 views
How to prove this 3-NAE-ICE is in NP
Input: A planar graph $G=(V,E)$ of maximum degree 3.
Output: The number of orientations such that no node has all the edges directed towards it or all the edges directed away from it.
I want to ...
1
vote
1answer
49 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 ...
0
votes
1answer
52 views
efficiency of verifier of Boolean
For a Boolean expression formula φ,
For a binary literal $i∈(0, 1)^l $
V(φ,i) is an Turing algorithm which decides whether i satisfies φ or not
...
1
vote
1answer
161 views
How to deduce the psition mapping of entries of a matrix?
I would be thankful if any peer shed light on me.
Assume that the mapping of a set is unknown. By knowing n number of E element sets and the transformed sets with positioned elements, How can I ...
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 ...
0
votes
0answers
17 views
Complexity of index calculus method
I read somewhere that complexity of index calculus method which calculates discrete logarithm over $Z_p^*$ is
$O\left(e^{(1 + o(1))(\sqrt{ln(p)\times ln(ln(p))}\;)}\right)$.
My question is, why ...
1
vote
2answers
96 views
Möbius function help
Given some large random integer k, how much longer would it take to determine the primality of k, then to calculate mobius(k), and how much longer would it take to factor k, then to calculate ...
1
vote
0answers
44 views
Is discrete ultralogarithm harder than discrete logarithm?
Is computing $g^{xy} \bmod{s}$ from $g^{x} \bmod{s}$ and $g^{y} \bmod{s}$ easier harder or the same level of difficulty as computing
$g\uparrow\uparrow(xy) \bmod s$ from from $g\uparrow\uparrow x$ ...
1
vote
1answer
40 views
Denesting Logarithmic expressions
$\log_7(\log_2(3)) + \log_7(\log_5(6)) + \log_7(\log_{11}(1/2)) = \log_7(-1) + \log_7(\log_5(3)) + \log_7(\log_{11}(6))$
This can only be simplified by using the sum to product rule and noticing that ...
0
votes
2answers
43 views
Can all programs be modeled as operations of elementary arithmetic operations on inputs?
In mathematics and computabiltiy theory, we treat
all inputs and intermediate results and final
outputs as natural number. While algorithms/programs themselves are considered natural
numbers, here we ...
0
votes
0answers
48 views
Can all programs reducible to ones with only arithmetic operations on inputs be simulated with polynomial overhead by arithmetic machine?
In Can all programs be modeled as operations of elementary arithmetic operations on inputs? and computabiltiy theory, I
asked:
we treat all inputs and intermediate results and
final outputs as ...
0
votes
0answers
15 views
Log-space reduction from EvenURch to Undirected Reachability
URch is: given an undirected graph G, and nodes x,y of G, is there a path from x to y in G?
EvenURch is given an undirected graph G, and nodes x,y of G, is there a path of even length(possibly ...
2
votes
2answers
98 views
transform traveling salesman problem into subgraph isomorphism problem
Lets say, I could solve subgraph isomorphism problem
in constant time.
How could I use this to solve traveling salesman problem?
aka... how to transform traveling salesman problem into subgraph ...
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 ...
4
votes
2answers
67 views
Minimum distance of a binary linear code
I need to find parameters $n$, $k$ and $d$ of a binary linear code from its Generator Matrix.
How can I find parameter $d$ efficiently?
I know the method that compute all the codewords and take ...
0
votes
1answer
46 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) ...
2
votes
1answer
24 views
knapsack with only odd elements
Is it feasible to solve the subset sum problem if all the elements are odd and we also know that whether odd or even no. of elements are used to form the sum
for example -
If i have the set -{ 9, 13 , ...
