Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
1
vote
1answer
32 views
proof of the rice's theorem
Let $P$ be any nontrivial property of the language of a Turing machine. Prove
that the problem of determining whether a given TM’s language has property $P$ is undecidable.
Proof:(This is from sipser'...
2
votes
0answers
15 views
Reducible from vertex cover for only some inputs
Suppose I have an NP problem, $\text{PROBLEM}(n)$, such that for certain values of $n$ I can get a reduction from vertex cover with $n$ vertices, and for others such a reduction is not possible (if $\...
0
votes
1answer
9 views
Is there an FPRAS for the number of min st cuts in general graphs?
Provan and Ball [1] showed that the problem of counting the number of minimum st cuts is #P-Complete. What is known about the problem of approximating the number of min st cuts? Is it possible to get ...
0
votes
0answers
14 views
Does $FL = FP$ if and only if $L = P$?
I believe the answer is yes. However, I fear I might be overlooking something. In general, what can one say about the equivalence of two complexity classes for decisions problems and the equivalence ...
1
vote
0answers
29 views
How can an arbitrary Turing machine running for $t$ steps be simulated in $O(n \log(n))$ steps?
I'm confused about a point regarding the Time Hierarchy Theorem. In order to establish the upper bound for this theorem it's necessary to show the following:
We're given $(\langle M \rangle, t)$ ...
0
votes
0answers
24 views
Space complexity for accepting word decision problem of DFAs
It is well known that the the decision problem $w \in \mathcal{L}(M)$ for a DFA $M=(Q,\Sigma, \delta, q_0,F)$ is in $\mathcal{O}(|w|)$. To proof this we assume that the successor state computation can ...
1
vote
2answers
24 views
NP-hardness does not imply lower bound, strictly speaking?
A problem is NP-hard iff every NP problem can be polynomially-time reduced to it.
Hardness is often intuitively explained as a lower bound. But it isn't, strictly ...
2
votes
1answer
31 views
Is it possible that $L=NP$?
According to Wikipedia and other sources, the question whether $L=P$ is an open problem, and of course everyone is familiar with the problem of whether $P=NP$. However, I found absolutely no ...
3
votes
2answers
64 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 a smaller upper ...
2
votes
0answers
11 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
30 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
32 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
55 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
52 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
36 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
46 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
9 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
43 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
62 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
76 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
20 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
27 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
31 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
85 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
156 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 ...
