Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

0
votes
0answers
12 views

Push down with log bound on stack

let LOG_CF be The class of all languages that has a Push down that use logn cells of stack for each input of length n Which languages are in this class? Is it equal to the class of context free ...
1
vote
0answers
7 views

How to find (real-valued) roots of matrix polynomial

Assume you have a fixed ($d=O(1)$ for that matter) degree matrix polynomial $$P(X)=A_0+A_1\cdot X+A_2\cdot X^2+\ldots+A_dX^d$$ Where $A_0,A_1,\ldots A_d\in\mathbb N^{n\times n}$ are given as input. ...
-2
votes
1answer
36 views

What is the complement of empty language?

Consider a turing machine that accepts the empty language. What will be the complement of the language generated by the above turing machine? A) Recursive B) Recursive Enumerable C) Non recursive ...
1
vote
0answers
24 views

Weakest reduction for P-completeness

It is common to define $P$-completeness with respect to logspace many-one reductions. I am looking for a complexity class $C$ such that if $C=P$ then all problems in $P$ are $P$-complete under ...
0
votes
1answer
27 views

closure property on languages

The above image, taken from planetmath.org, describes the closure property on REG (regular), DCFL (deterministic context-free), CFL (context-free), CSL (context-sensitive), RC (recursive), RE ...
4
votes
0answers
12 views

Fastest known complexity for combinatorial ILP algorithm?

I'm wondering, what is the best known algorithm, in terms of Big-$O$ notation, to solve Integer Linear Programming? I know that the problem is $NP$-complete, so I'm not expecting anything polynomial. ...
0
votes
1answer
76 views

Some questions about NP / coNP / CSP

I need help with the following mock exam questions. True or false? 1.) If a non-trivial $(\neq \emptyset, \Sigma^*)$ finite set is NP-complete, then $P = NP$. True. Every finite set is in $P$ and ...
1
vote
1answer
34 views

IS and matching

I have 2 different but similar problems, one belongs to NP and one to L and I don't understand why. First problem: Input: an undirected graph G with n^2 vertices. Question: Is there exist in G a ...
3
votes
2answers
81 views

Overlap between theory and systems fields in CS

I have finally had some serious graduate-level exposure to CS Theory and loved it. I really enjoyed complexity theory (time and space complexity, the different classes, reductions to prove ...
1
vote
2answers
42 views

Complexity of nested loops [duplicate]

I'm trying to figure out the complexity of the following algorithm. ...
0
votes
2answers
61 views

Tracking object problem

I have to track an object. I m confused whether its a P Problem or NP Problem?. The object is a piece of paper of white color, which matches with the background color I m working in, and also the ...
5
votes
0answers
132 views

Travelling with the most efficient path

A friend of mine actually asked me a very interesting computer science related question, and I have been stuck on it for a long time. The problem is: you have to travel $1000$ km. The only gas ...
5
votes
3answers
451 views

Proof that Hamiltonian cycle/circuit with a specified edge is NP-complete

I'm a little stuck on this question, any help would be appreciated! Given that the Hamiltonian Path (HP) and the Hamiltonian Circuit/Cycles (HC) problems are known to be NP-complete, show that HCE is ...
-4
votes
1answer
44 views

Proof problem is NP [on hold]

Hi need help to proof: For each A,B problems , if A ≤p B , and B ∈ NP then A ∈ NP Thanks.
7
votes
0answers
154 views

Choosing a subset of binary variables to maximize the sum of the highest $K$

Given $N$ probabilities $P_1,\dots,P_N$ and rewards $R_1,\dots,R_N$ and the integers $M,K$ $(N>M>K)$ as input, define the random variables $X_1,\dots,X_N$ as $$X_i=\begin{cases} R_i & ...
-1
votes
2answers
58 views
1
vote
1answer
87 views

Karp reduction from 3-SAT to 3-PARTITION

I want to show that this problem is NP-complete: partition a set of 3n real numbers to n partitions of 3 number which each partition has the same sum of its members. I want to reduce 3-SAT to this ...
2
votes
1answer
98 views

Is it true that $FP^{NP[log\cdot n]} = FP^{NP}$ if $P = NP$?

Is it true that $FP^{NP[log\cdot n]} = FP^{NP}$ if $P = NP$? If I understand the polynomial hierarchy correctly, then, if $P = NP$, all complexity classes collapse to one class. Therefore the above ...
1
vote
1answer
33 views

Decrease space complexity, how will time complexity increase?

I have a problem whose lower bound of problem complexity is proven to be $O(n+m)$ (n < m) and I also come up with an algorithm whose time complexity is $ O(n+m)$, space complexity is $ O(n)$. (All ...
1
vote
1answer
14 views

The number of operations of Explicit and Implicit Euler for 1D hear equation

I'm studying with "Numerical Solution of Partial Differential Equations by K.W.Morton and D.F.Mayers". On page 25, it says "2(add) + 2(multiply) operations per mesh point for the explicit algorithm ...
2
votes
1answer
34 views

Definition of $D^P$?

What is the definition of the complexity class $D^P$? In recent papers I sometimes read $D^P$ but could not find a definition of it. Unfortunately Complexity Zoo does not give one, too. Is it the ...
1
vote
0answers
31 views

Using algebraic structures to solve computer science questions (xpost from math.se) [closed]

This is a cross post from here. I would like to know of some examples or references where algebraic ideas have been used in complexity theory or the like. Examples would be parallels of ...
0
votes
1answer
62 views

Example of a boolean function

Is there an example of real polynomial representation of a Boolean function with $4$ variables whose polynomial degree is $2$ that depends on $4$ variables?
0
votes
0answers
14 views

Block sensitivity and degree

$\newcommand{\bs}{\mathrm{bs}}$What is the largest gap known between block sensitivity ($\bs(f)$) of a boolean function ($f$) and degree of a polynomial ($\deg(f)$) that represents/approximates it? ...
0
votes
3answers
75 views

Given a minimum vertex cover can we find all the others in polynomial time?

Having found one minimum vertex cover of a connected undirected graph, is there a known polynomial-time algorithm for finding all the other minimum vertex covers of the graph, or is this problem ...
1
vote
0answers
50 views

Is the multiset - subset sum problem variant not in NP?

If the input for a subset sum problem is a multiset (with repetitions) instead of a set (without repetitions), e.g. Set $a = ...
2
votes
1answer
41 views

Complexity of a knapsack variant

Consider the following traditional integer knapsack problem: $\max \sum_{i=1}^k p_i \cdot x_i\\ \text{s.t.} \sum_{i=1}^k w_i \cdot x_i \leq W \\ x_i \in \{0,\ldots,k_i\} \text{ for each } i$ Now ...
1
vote
0answers
39 views

Deciding coprimality of integer pairs [on hold]

Given $a,b$, I know that computing $GCD(a,b)$ takes $O(log_2^{1+\epsilon}(ab))$ complexity. If we just want to decide $GCD(a,b)=1\mbox{ or }\neq1$ with certainty or with certain error $\epsilon$, ...
5
votes
2answers
59 views

MAX,MAJ variants of NP complete problems

We know that MAJSAT is PP-complete. Is it generally true that given an NP-complete problem, its majority variant is PP-complete? For example, MAJ-Set-Splitting: are the majority of partitions of ...
3
votes
3answers
98 views

Termination in infinite-time

Does it make sense to speak of algorithms that take an infinite amount of time to terminate? In particular, suppose we have a loop with a bound function that is initially positive and is decreased ...
1
vote
1answer
51 views

Lower bound on approximation degree in Nisan-Szegedy

In Nisan and Szegedy's 1994 paper "On the degree of boolean functions as real polynomials"[1] Lemma 3.8, how does proof work for $\widetilde{\deg(f)}\geq \sqrt{\,\tfrac16\mathrm{bs}(f)\,}$? It ...
1
vote
1answer
25 views

Different boolean degrees polynomially related-2?

Essentially similar question to here Different boolean degrees polynomially related? (change being error condition $\epsilon\in(0,1)$). Let $p$ be the minimum degree (of degree $d_f$) real polynomial ...
1
vote
1answer
21 views

Kth largest subset for small K

The $K$th Largest Subset problem is often given as an example of an NP-hard problem. However, the assumption is that $K$ is unconstrained, and can be as large as $2^n$. Clearly, if $K \le 3$ the ...
1
vote
1answer
50 views

Relations among different boolean approximations

Essentially similar question to here Different boolean degrees polynomially related? (change being error condition $\epsilon\in(0,1)$). Let $p$ be the minimum degree (of degree $d_f$) real polynomial ...
3
votes
1answer
58 views

Is a Karp-Levin reduction a Levin reduction?

My understanding is that Karp many-one reductions are more general than Levin many-one reductions, and that Levin many-one reductions must allow for the number of certificates for a problem $A$ ...
0
votes
1answer
24 views

Reductions where the number of certificates from one problem can be computed for another to varying degrees

Let $A$ and $B$ be two decision problems in $NP$. Consider three cases: (1) For any instance of problem $A$, one can produce, in polynomial time, an instance of problem $B$ having exactly the same ...
-1
votes
1answer
72 views

Pumping Lemma Proof by contradiction [duplicate]

So, hi guys! I have a language which I am trying to prove that it is not regular using the Pumping Lemma. I am pretty new into the lemma so I would appreciate any help.The language is $$L = \{w | w ...
3
votes
1answer
44 views

What is the relation between arithmetic circuits and straight line programs?

One definition of arithmetic circuits is as follows: An arithmetic circuit $\Phi$ over the field $\mathbb F$ and the set of variables $X$ usually, $X = \{x_1, \dots , x_n\}$) is a directed ...
1
vote
1answer
43 views

Different boolean degrees polynomially related?

Let $f$ be a Boolean function. Let $p$ be the minimum degree real polynomial that represents $f$ with degree $d_f$. Let $p_\epsilon$ be the minimum degree real polynomial with degree ...
1
vote
1answer
64 views

Diophantine equations and P=NP

It was proven that the problem of determining whether a given Diophantine equation has a solution is undecidable (and therefore has no polynomial time algorithm). But we can check proof certificates ...
0
votes
1answer
30 views

NP Problem and reduction [duplicate]

I've read that "Every problem in NP can be reduced to every NP-complete problem". I want to know why the term "Every" is important.If we have one problem in NP that is reduced to one NP complete ...
33
votes
8answers
4k views

What would be the real-world implications of a constructive $P=NP$ proof?

I have a 5000-ft-view understanding of the $P=NP$ problem and I understand that if it were absolutely "proven" to be true with a provided solution, it would open the door for solving numerous problems ...
1
vote
1answer
41 views

Lower-bounds of a given problem

I have the following problem: You have n objects that have identical weight except for one that is a bit heavier than the others. You have a balance scale. You can place objects on each side ...
14
votes
2answers
1k views

Why do we believe that PSPACE ≠ EXPTIME?

I'm having trouble intuitively understanding why PSPACE is generally believed to be different from EXPTIME. If PSPACE is the set of problems solvable in space polynomial in the input size $f(n)$, ...
0
votes
1answer
27 views

Limiting capacity of knapsack to a polynomial function of elements in the Knapsack problem

I saw somewhere that if we limit the capacity (weight) of the knapsack to a polynomial function of elements then the class of the problem changes to P, but it didn't say why. I can't figure out why is ...
8
votes
1answer
100 views

Group isomorphism to graph ismorphism

In reading some blogs about computational complexity (for example here)I assimilated the notion that deciding if two groups are isomorphic is easier than testing two graphs for isomorphism. For ...
0
votes
0answers
15 views

On Randomized/Quantum $\mathsf{NP}$-complete subexponential algorithms

Could the ETH be true and we still have randomized/quantum subexponential algorithms for $\mathsf{NP}$-complete problems?
16
votes
0answers
746 views

Is it NP-hard to fill up bins with minimum moves?

There are $n$ bins and $m$ type of balls. The $i$th bin has labels $a_{i,j}$ for $1\leq j\leq m$, it is the expected number of balls of type $j$. You start with $b_j$ balls of type $j$. Each ball of ...
1
vote
1answer
2k views

Algorithm to write a dictionary using thousands of words to find all anagrams for a given string with O(1) complexity

Problem Statement: Suppose we have a thousands of words and we need to maintain these words in a data structure in such a way that we should be able to find all anagrams for a given string. I tried to ...
3
votes
1answer
41 views

Minimal complexity for pairing two comparable sets with comparability restrictions

A project at university (whose deadline has passed by now) presented the following problem: Consider two finite sequences of (not necessarily distinct) real numbers $a_1,\ldots,a_n$ and ...