Computational complexity, a part of theoretical computer science.
0
votes
0answers
13 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
41 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 ...
1
vote
1answer
145 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 ...
0
votes
0answers
15 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
0answers
40 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$ ...
0
votes
0answers
14 views
Fastest way to run prim's on a growing range of coordinates
I was hoping someone could give me a general method for computing the MST for a problem that works from input that is formatted as such:
...
2
votes
2answers
43 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
42 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
2answers
37 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
10 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 ...
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
39 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 ...
7
votes
3answers
126 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
49 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
39 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
12 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
votes
0answers
19 views
Decidable, recognizable question? [duplicate]
I need to prove if the following language decidable? Is it recognizable? Is it co-recognizable?
Without using rice.
i have an idea with reduction to ATM but i dont know how,
please help me
thanks .
...
-4
votes
0answers
41 views
Growth of Functions, Complexity, Algorithm Big O, Omega and Theta [closed]
Please help:-
For each of the following functions, determine the appropriate $\mathcal{O}$, $\Omega$ and $\Theta$. Show
your work (i.e find $k$; $C_0$ for \mathcal{O} and $l$, $C$ for $\Omega$ using ...
-1
votes
0answers
38 views
How find $k$-th smallest number in $O(\log n)$ time in python [closed]
I need to give an $O(\log n)$ time implementation of a method called ithSmallest(i) that takes an
integer $i$ and returns the $i$-th smallest value in the tree. (Assume that the tree is balanced (i.e. ...
2
votes
1answer
21 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 , ...
2
votes
2answers
73 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 ...
0
votes
0answers
14 views
Dynamic programming and time complexity
I was wondering if you might have some insight into a problem, where we consider an optimization problem:
max ∑f*j*(x*j*) from j=1 to n of s.t. ∑ j=1 to n of xj <=B
xj>=0, integers
where B is a ...
1
vote
1answer
30 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 ...
2
votes
0answers
42 views
Solving recurrence relation of algorithm complexity?
Supposing I write an algorithm that results into this kind of recurrence relation
$$\left\{ \begin{array}{ll}
T(0)=T(1)=1 \\
T(n)=T\left(\lfloor n/2 \rfloor \right)+T\left(\lceil n/2 ...
1
vote
0answers
49 views
Expansion in powers
Let $n=2k, k \in Z_+$. Let
$$P_k\left(\frac{t}{\sqrt n}\right)=n!\sum_{\begin{smallmatrix} n_1+\ldots+n_k=n \\ ...
0
votes
1answer
69 views
understing Cook theorem and input length
Following is my understanding of Cook theorem.
Let P be a $\mathcal{NP}$ problem.
And let M be a polynomial NDTM for P,
$$
M(x) = \left\{
\begin{array}{ll}
1\text{ if x∈ P}\\
0\text{ ...
1
vote
1answer
50 views
Proving that a function is negligible
In mathematics, a negligible function is a function $\mu(x):\mathbb{N}{\rightarrow}\mathbb{R}$ such that for every positive integer $c$ there exists an integer $N_c$ such that for all $x > N_c$,
...
1
vote
1answer
39 views
Restricted partitions?
Suppose I have an integer N and i want to partition it, it must only involve numbers in set $S$ and the number should appear only once.
For example if $N = 12$ and $S = \{3, 5, 7\}$ the answer should ...
0
votes
1answer
76 views
Solving a recurrence relation using Z transform
I'm trying to solve the following recurrence using Z transforms:
For $n\in \mathbb{N}^{*}$
$T(n)=1\ for\ n< 4$
$T(n)=T(\lfloor \frac{n}{4} \rfloor)+T(\lfloor \frac{3n}{4} \rfloor)+n\ for\ n\geq ...
2
votes
2answers
97 views
Would it be possible to concoct a “harmful” axiom?
Suppose I run an automated theorem prover. It begins with the axioms of ZFC, and using a random number generator, it proves more theorems, and it runs for two days. At the end of the second day, it ...
3
votes
1answer
31 views
Computing the period of a fraction polynomial in the number of digits
So I have a fraction a/b that is known to be repeating. How do I compute the period of the repeating decimal in polynomial-time in the number of digits of A and B?
5
votes
1answer
50 views
Maximal Zero Sums Partition
You are given $n$ numbers between $-n$ and $n$, the sum of numbers is $0$. Divide the given sequence on disjoint subsequences in such a way that each subsequence has zero sum. Each element should ...
0
votes
1answer
64 views
algorithm and Cook theorem
Let $A$ be a set of decision algorithms which are running in polynomial time and which takes natural numbers as inputs.
$x\in A$ if and only if
for $i\in N$
$x(i)=0$ or $x(i)=1$
...
0
votes
1answer
49 views
About Cook–Levin theorem
I want to check whether I understand the Cook-Levin theorem fully (using the Travelling Salesman Problem as an example).
Given a weighted graph $G$ and an number $L$, the a Travelling Salesman ...
1
vote
2answers
38 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 ...
1
vote
1answer
41 views
What does it mean for a function to be polynomially bounded
There is a definition in my notes and says,
When functions are polynomially bounded, the initial conditions (the value on
small inputs) do not make a difference for the solution in ...
2
votes
1answer
69 views
Games for which the Lemke-Howson algorithm provides incomplete results
I am exploring a large number of 2-player games. The Lemke-Howson algorithm is computationally very reasonable, and is able to find many equilibria. On the other hand, I know that there are equilibria ...
1
vote
1answer
148 views
Well formed formulas of all mathematical proof
Last week, I asked the "automated proof-checking machine." Many answered that automated proof-checking machine already exists in first-order theory.
However I have still question. For the operation ...
0
votes
1answer
76 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
36 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
2answers
89 views
Automated proof-checking machine
In the future, theoretically, is it possible to make an automated proof-checking machine?
It means, given mathematical axioms and definitions, the computer can decide that a proof is correct or not, ...
0
votes
1answer
66 views
Solving the following recurrence relation
I have a recurrence relation, it is like the following:
$$
T(e^n) = 2\cdot T(e^{n-1}) + e^n, \text{ where $e$ is the natural logarithm}
$$
To solve this and find a Θ bound, i tried the following: I ...
1
vote
2answers
50 views
The use of master theorem appriopriately
I have a recurrence relation and trying to use master theorem to solve it. The recurrene relation is:
$$T(n) = 3T\left(\tfrac n5\right) + \sqrt n$$
Can i use the master theorem in that relation? If ...
1
vote
2answers
52 views
Sequences and Languages
Let $U$ be the following language. A string $s$ is in $U$ if it can be written as:
$s = 1^{a_1}01^{a_2}0 ... 1^{a_n}01^b$,
where $a_1,..., a_n$ are positive integers such that there is a 0-1 ...
2
votes
1answer
36 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 ...
4
votes
2answers
74 views
How to recover a shuffled matrix
Suppose that I have a matrix $A$. $A$ can be a rating matrix. That is, $A(i,j)$ is the rating user $i$ has given to item $j$.
Suppose that I shuffle the rows and columns of matrix $A$ and get ...
2
votes
1answer
25 views
What's the relationship between the Ham Sandwich Theorem and the PPAD Complexity Class?
Wiki says:
"The Ham sandwich theorem is known to lie in PPAD but it remains an open question as to whether or not it is PPAD-complete."
What is the computational problem based on the Ham Sandwich ...
1
vote
1answer
30 views
Time complexity of a modulo operation
I am trying to prove that if $p$ is a decimal number having $m$ digits, then $p \bmod q$ can be performed in time $O(m)$ (at least theoretically), if $q$ is a prime number. How do I go about this?
A ...
1
vote
2answers
141 views
Solving a recurrence relation using master method
I know that the Master theorem is used for the recurrence relations of the form:
$$T(n) = aT(n/b) + f(n)$$
In my question, I am supposed to solve the following recurrence relation by using Master ...
