Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
2
votes
0answers
23 views
Complexity of multiplying two integers of size $n$ and $m$
The multiplication of two integers of size $n$ can be done in time $O(n \cdot \log n \cdot \log\log n)$ using FFT method.
If the two integers have different sizes $n$ and $m$, does an upper bound ...
2
votes
0answers
10 views
Complexity of STRIPS planning for finding optimal solution: PSPACE-complete or NP-complete?
I am reading the two articles below to try to figure out whether STRIPS are NP-complete or PSPACE-complete. Specifically, I am trying to figure out the complexity of finding optimal solutions using ...
0
votes
0answers
27 views
Decidablity of time complexity
Let $t:\mathbb{N}\rightarrow\mathbb{N}$ be a time constructible function with $t(n)\geq n + 100$. Show that there is no TM $T$ that given the gödel number of another TM $M$, decides wether or not M is ...
0
votes
1answer
30 views
Is TSP a more detailed form of the “Set Inclusion” question?
Set Inclusion
GIVEN: set of cards, some with blue backs, and each with a positive, integer face value.
QUESTION: Are there any [blue-backed cards] with a [face value <= L]?
2 independent ...
1
vote
1answer
48 views
What is the fastest algorithm to establish whether a linear system in $\mathbb{R}$ has a solution?
I know the best algorithm to solve a linear system in $\mathbb{R}$ with $n$ variables is Coppersmith-Winograd's algorithm, which has a complexity of
$$
O\left(n^{2.376}\right).
$$
How much easier is ...
1
vote
2answers
49 views
Is $f(cn)$ always $O(f(n))$ for constant $c$ and any function $f$?
This seems to be true for any function I can think of, but I'm not quite sure how to prove it. Is there a proof of this proposition for any such function or a counter-example?
1
vote
1answer
33 views
Space and time complexity of $L = \{a^nb^{n^2} \mid n≥1\}$
Consider the following language:
$$L = \{a^nb^{n^2} \mid n≥1\}\,$$
When it comes to determining time and space complexity of a multi-tape TM, we can use two memory tapes, the first one to count $n$, ...
1
vote
1answer
44 views
RAM BSS model based (or its variant) computer recognizing Boolean languages
Can any RAM BSS model based machine, or machines which are variants, recognize boolean languages(languages such as P, NP, or the like)? If so which languages are recognizable by RAM/BSS nachines, or ...
0
votes
1answer
27 views
Why is a heap better than a linked list for implementation of a priority queue?
Using a heap, you have O(log(n)) insertion and O(log(n)) removal. Using a linked list, you have O(n) insertion and O(1) removal.
Why is it better to have log-n for both than n for one and constant ...
0
votes
0answers
8 views
forming recurrence equations from code
Please could someone help me with understanding how to form recurrence equations when reading code? I'm having some trouble in my class:
...
1
vote
1answer
15 views
Multi-variate complexity semplification
I developed an algorithm with the following multi-variate complexity:
$$O((k^n+kn)l^{kn}),$$
where $n,k,l$ are variables.
I have very little knowledge of complexity theory, and I'm not sure whether ...
1
vote
1answer
32 views
How does quicksort with 3-way partitioning ~ $(2 ln 2) NH$ become linear time complexity with many duplicated keys?
From Algorithms 4th:
Quicksort with 3-way partitioning uses ~$(2\ln 2)NH$ compares to sort $N$ items, where $H$ is the Shannon entropy, defined from the frequencies of key values.
$ H = -(p_{1}\...
-1
votes
0answers
42 views
Reduction from “restricted-3-partition” to “k-graph-partition”
I need a reduction from “Restricted-3-partition” to “k-graph-partition” that can be done in polynomial time, but I have absolutely no clue how to start this off. Can anyone help me out with an ...
5
votes
2answers
114 views
Why researchers don't study the parameterizations of the problems unlikely to be NP-Hard?
I have seen the parameterization of the very well known problems like vertex cover, hitting set etc which are NP-hard (NP-complete precisely). Many researchers in the past have been studied the ...
0
votes
3answers
61 views
Which of the following problems can be reduced to the Hamiltonian path problem?
I'm taking the Algorithms: Design and Analysis II class, one of the questions asks:
Assume that P ≠ NP. Consider undirected graphs with nonnegative edge
lengths. Which of the following problems ...
0
votes
2answers
59 views
Which of the following statements are true for the given special cases of the Traveling Salesman Problem?
I'm taking the Algorithms: Design and Analysis II class, one of the questions asks:
Which of the following statements is true?
Consider a TSP instance in which every edge cost is either 1 ...
0
votes
0answers
6 views
Smallest Circuit for Square of Sparse Symmetric Matrix
I have an n by n symmetric matrix, and I would like to compute its square in as small a circuit complexity as possible. It's sparse: there are sqrt(n) nonzero entries in each row/column, so the input ...
0
votes
0answers
19 views
Is the succinct version of P-complete problems out of P?
Consider the succinct versions of the P-complete problems as a Boolean circuit which represents its input in exponential more succinct ways. Could these succinct versions are in P or out of P?
1
vote
0answers
13 views
Without using the Space Hierarchy Theorm is there any other way to prove that NL is not equal to PSPACE
From what I know there is no alternate way that NL is not equal to PSPACE. If possible can you link a paper or some book recommendations to show that this is the case.
Thank You
Akash
-1
votes
0answers
7 views
How Polynomial-time function is precisely the class of polynomial reductions, which are used in turn to define the class of NP-complete problems?
Polynomial-time function problems are fundamental in defining polynomial-time reductions, which are used in turn to define the class of NP-complete problems.
This question was asked in my assignment, ...
0
votes
1answer
54 views
Is there a useful algorithm with a decreasing asymptotic time?
Algorithmic complexity is usually increasing and almost always strictly increasing based on input size. This is logical since algorithms take time to execute steps, and for almost all problems, the ...
3
votes
2answers
56 views
The complexity of the reachability-coreachability analysis of a finite state machine
Let $A = \{\Sigma,Q,\delta,q_{0}, Q_{m}\}$ be a finite state machine (FSM). A state $q \in Q$ is reachable if there exists a string $s \in \Sigma^{*}$ such that $\delta(q_{0},s) = q$. The state $q$ is ...
-1
votes
0answers
15 views
Is NL a subset of PSPACE?
In my research I have not found a concrete explanation whether NL is truly a subset of PSPACE.
However, I would like some help or pointers like a book or a paper/web link to cover what I could have ...
1
vote
0answers
21 views
Algorithm to split a grid into different shapes of similar area
I was wondering if any of you know of any algorithm which allows me to split a grid into smaller shapes of a similar area.
I have a grid and a few points, these points determine the center of the ...
1
vote
0answers
26 views
Why full Chomsky hierarchy is so detailed, if there are decidable recursive languages?
One can have a look on the Chomsky hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy , especially the inset named "Automata theory: formal languages and formal grammars" at the bottom of the ...
1
vote
2answers
99 views
If a non-deterministic Turing machine runs in f(n) space, then why does it run in 2^O(f(n)) time?
Assuming that f(n) >= n.
If possible, I'd like a proof in terms of Turing machines. I understand the reason why with machines that run on binary, because each "tape cell" is a bit with either 0 or 1, ...
1
vote
1answer
29 views
Why any problem can be reduced to SAT is NP-Complete?
I have a book statement says the title, I don't understand it. From my current understanding if a problem A can be reduced to a problem B then it only means B is at least as difficult as A.
0
votes
2answers
84 views
How to generate an instance for an NP_hard proof, where each element has two inputs?
I want to prove the NP-hardness of an scheduling problem. The problem seems to be NP-hard in the ordinary sense, so I am trying with the Partition Problem, precisely the Equal Cardinality Partition (...
5
votes
1answer
87 views
Why is Adleman's molecular algorithm for Hamiltonian Path linear?
In Adleman's 1994 paper (archived), he describes a method of manipulating DNA molecules in a lab that results in a solution to the Hamiltonian Path problem with high probability.
He claims that "The ...
1
vote
0answers
5 views
$NC$ and $FNC$ oracles low for functional and Stockemeyer classes respectively?
We know $P^{NC}=P$ and $FP^{FNC}=FP$ hold. Do $FP^{NC}=FP$ and $P^{FNC}=P$ hold?
3
votes
2answers
46 views
Given a set $A$ of sets find a minimal set $B$ of pair-wise disjoint sets such that each set in $A$ can be expressed as a union of sets in $B$
I recently thought of the following problem:
Given a set $A$ of sets find a minimal set $B$ of pair-wise disjoint sets such that each set in $A$ can be expressed as a union of sets in $B$.
For ...
0
votes
1answer
22 views
Why $xx^TM$ requires $O(dk)$ operations?
Suppose $x \in \mathbb{R}^d$ and $M \in \mathbb{R}^{d \times k}$.
Why $xx^TM$ requires $O(dk)$ operations?
4
votes
2answers
166 views
Solving “ Tricolor Arrangement ” Efficiently
A rectangular board with three rows and $n$ columns is filled with $3n$ counters, of which $n$ are red, $n$ are white, and $n$ are blue. The object is to rearrange the counters to have counters of ...
0
votes
0answers
15 views
What would be the consequences if P=NL
I haven't found anything in the literature that suggests what would happen if that is the case.
Thank you,
Akash
0
votes
1answer
22 views
Show that $A_\mathrm{LBA}$ is PSPACE-Complete?
I want to show that $A_\mathrm{LBA}$ is PSPACE-Compelte.
Say we proved it is in PSPACE. Now for PSPACE-HARD:
I had an idea, which was very similar to some solution i found on the web- say we have a ...
2
votes
1answer
148 views
What does a proof that Co-NP =P entail for the NP versus Co-NP question
What I wonder is what exactly would it entail. Would it,for instance imply that P=NP or would there be different consequences,I haven't found any assorted consequences so far in my research.
Thank You,...
0
votes
1answer
38 views
How do you find set of keywords present in set of words in linear time or log time?
I am trying to optimize a program, where I need to know whether a given set of keywords present in the set of words. I believe using the dictionary is the only way to optimize it. Any other technique ...
2
votes
1answer
152 views
Prove that every CFL is decidable in O(n) space
this question came up while a group of students at my school were studying for our qualifying exams. The question on an old exam was:
Prove that every context free language $A$ is in $\mathrm{SPACE}...
0
votes
1answer
25 views
Complexity of an instance of a NP-complete problem
I am trying to prove the NP-Completeness of problem [A].
I know there is a well-known NP-Complete problem called problem [B].
I can model [A] into an instance of [B] ([B] is a very general problem ...
2
votes
1answer
21 views
Given a set of intervals on the real line, find a minimum set of points that “cover” all the intervals
I've been trying to find an efficient way to solve the problem of finding a minimum (not minimal) set of time points that cover a given family of intervals on the real line, that is, for each interval ...
1
vote
1answer
21 views
Verifier for A_tm in polynomial time - how to formally prove it does not exist?
How would you formally prove the non-existance of a polynomial time verifier for $A_\mathrm{TM}$?
I mean we can't just say that in order to read a certain certificate we need more than poly-time ...
0
votes
1answer
29 views
Complexity of linear programming with restricted quadratic constraints
A problem instance is a linear program with the following kind of quadratic inequalities allowed: For some of the variables $x_i$, there is a variable $s_i$ (intuitively for approximating $x_i^2$, and ...
-1
votes
0answers
45 views
Is 3-SAT strongly NP-complete
Can we consider 3-SAT to be strongly NP-complete? In the knapsack problem, we have a polynomial time algorithm in input size when we consider unary encoding of the input. This makes it weakly NP-...
1
vote
0answers
16 views
Why is the “general notion of a reduction […] inherent to the notion of self-reducibility”? [migrated]
While reading "Computational Complexity: A Conceptual Perspective" by Oded Goldreich, I have come across the following passage, which I simply cannot get my head around:
Note that the general ...
1
vote
1answer
61 views
Without using the Time Hierarchy Theorem, is there any other way to prove P /= EXP
I haven't found any way to show this was the case (that P/=EXP, without using the Time Hierarchy Theorem)
If you can find a way to show this, can you give a short explanation of this,and also if ...
1
vote
1answer
17 views
Reducing 3SAT to MAX-3SAT
I have the following problem:
Consider the MAX-3-SAT problem: given a Boolean function in
Conjunctive Normal Form (CNF) determine the maximum number of clauses
that can be satisfied. Prove that ...
8
votes
3answers
936 views
Strassen algorithm for matrix multiplication complexity analysis
I see everywhere that the recursive equation for the complexity of Strassen alg is:
$$T(n) = 7T(\tfrac{n}{2})+O(n^2).$$ This is not so clear to me.
The parameter $n$ is supposed to be the size of the ...
0
votes
0answers
23 views
Proofs of the form “$A, B \in \mathcal{NP}\setminus{\mathcal{P}}, \ A, B \not\in \mathcal{NP-C}, \ A \not\leq_p B$”
I'm currently learning about complexity classes and I have a few general questions:
Assume $A, B \in \mathcal{NP}\setminus{\mathcal{P}}, \ A, B \not\in \mathcal{NP-C}$
are people generally ...
4
votes
1answer
80 views
More complicated resources than time and space complexity
The wikipedia page on computational resources states that there are many different resources that have been defined:
In computational complexity theory, a computational resource is a resource used ...
1
vote
1answer
26 views
Number of divisors of a number - in NP?
I'm trying to show that the language {(m,n)|m has exactly n divisors} is in NP.
The input (m,n) is in binary.
The non-deterministic Turing machine for the language would be:
1) Guess the prime ...
