Tag Info

New answers tagged

1

Let Vertex-Cover = $\{ <G, k> : G$ has a vertex cover of size k$\}$ Given an instance $<G(V, E), k>$ of Vertex-Cover construct an instance $<G'(V', E'), k+2>$ of $K_4$-Cover: 1) Set $V' = V \cup \{x, y\}$. 2) Set $E' = E$ 3) Add the edge (x, y) to E' 4) For each edge $(u, v)$ in E', add the edges $(x, u), (x, v), (y, u), (y, v)$ ...


0

The Monte=Carlo method is actually a FPRAS, at least according to my definition of FPRAS, so that is an example. Barvinok's algorithm is probably too hard to explain without a long answer and some higher level background math, but I do know that Barvinok came up with a (still farily complicated) way to count the number of integer points exactly in a convex ...


0

You could try programming a sieve to mark all the composites, then add up the unmarked numbers. To do that, you'll need a list of primes up to $10^7$. In order to get that, you could program a sieve... This method is obviously pretty memory-intensive, but it's certainly faster than prime-testing each integer from $10^{10}$ to $10^{14}$.


0

Yes. a+b and a-b are each co-prime to each of a and b. Therefore, you know that none of the prime factors of a or b is a factor of a+b or a-b. Therefore, there is no need to test a+b or a-b for those factors.


1

Since we only care about natural numbers, try the first few: $f(1)=15, g(1)=1$, so if this works, $C \geq 15$. $f(2)=33, g(2)=8$. $15$, works here. Now that we have a $C$ that should work, we want to check the $Cg(n)=15n^3 \geq f(n)$ for $n=1,2,...$. $f(n) \leq 5n^2+3n^2+7n^2=15n^2 \leq 15g(n)=15n^3$ for $n\geq 1$.


1

This means that for some $N_0$ and some $c$ you have that whenever $n \ge N_0$: $$ 5 n - 2 \ge c (16 n + 32) $$ In this case you can take e.g. $N_0 = 100$, and set up the equation: $$ 5 N_0 - 2 = c (16 N_0 + 32) $$ which gives $c = 83 / 272$. So if $n \ge 100$: $\begin{align} (5 n - 2) - \frac{83}{272} (16 n + 32) &= \frac{2 n - 200}{17} \\ &\ge ...


1

The existence of one-way functions implies $\mathbf{P}\ne \mathbf{NP}$, hence if $\mathbf{P} = \mathbf{NP}$, one-way function do not exist. In turn, the security of most cryptographic constructs (pseudorandom generators, encryption schemes, ...) implies the existence of one-way functions, so they cannot exist if one-way functions do not exist. Note that the ...


6

Must an algorithm that decides a problem in NP also be able to construct a solution for that problem which can then be verified in polynomial time? No, but a solution can be easily derived using the decision procedure for NP problems because all NP-complete problems are downward self-reducible and all NP problems can be reduced to NP-complete problems. ...


11

If you could decide SAT problems in polynomial time, then you could also find a solution (for those instances that have them) in polynomial time. Namely, if Boolean expression $A$ is satisfiable and $x$ is a variable appearing in $A$, choose one of the expressions $A|_{x=T}$ and $A|_{x=F}$ (obtained by setting $x$ to "true" or "false" respectively) that is ...


1

Expanding on Mark Bennet's comment: Using the information on this link (by adapting the proof to Permanents) When you row reduce a determinant, this happens $$\det(A)=\left|\begin{matrix} a_{11}&\cdots&a_{1n}\\ \vdots&\ddots&\vdots\\ b_{i1}&\cdots&b_{in}\\ \vdots&\ddots&\vdots\\ a_{n1}&\cdots&a_{nn}\\ ...


2

Under the condition that every $x_k$ is non-negative, if $K \geq 0$ then set $x_1 = \cdots = x_m = 0.$ Then $a_1x_1 + \cdots + a_mx_m = 0 \leq K$. If $K < 0$ and one of the coefficients $a_k$ is negative, set $x_k \geq \frac{K}{a_k}$ (so that $a_kx_k \leq K$) and set all other $x_i=0$. If $K < 0$ and $a_k \geq 0$ for every $k$, then there is no ...


1

There are some standard solutions to k-truncated SVD problem, including the power iteration algorithm and Krylov subspace methods. Also, there are lots of randomized methods (with name "sketching") to speedup this method with sacrifice of the accuracy. We refer to the paper below: Halko N, Martinsson P G, Tropp J A. Finding structure with randomness: ...


0

The professor who assigned the project should be happy to provide appropriate references. I do not know about your particular fieds, but for general complexity theory the classic is Papadimitriou and the modern is Arora-Barak.


0

The "mod" operator in computer languages is simply the remainder. For example, 17 mod 3 = 2 because 17 / 3 = 5 rem 2 which in turn means 17 = 3 * 5 + 2


1

First of all, note that no instance itself is NP-complete. I will reformulate your question in a way that makes sense, hopefully capturing what you meant to ask. Let Strict Max 2-SAT be the problem whose instances are those in Max 2-SAT where all clauses have 2 variables. The question is whether Strict Max 2-SAT is NP-hard. We can reduce Max 2-SAT to ...


0

If a single 2-SAT clause contains the same variable twice, then either both literals are equal (in which there is only one way to set the variable, which reduces the 2-SAT formula), or one literal is the negation of the other, in which case any way you set the variable will satisfy that clause and thus that clause can be deleted. So yes, in general, you can ...


0

The algorithm isn't completely specified -- you say that you continue until the remaining number is prime, but not how you tell that this is the case. You use primes but don't explain how they are generated. You also don't say what you mean by time complexity. I will outline two versions of the algorithm and give the worst-case arithmetic complexity of each, ...


2

I think you are correct. The chromatic index is easy to "approximate". I believe that the authors meant $\chi(L^k(G))$ instead of $\chi'({L}^k(G))$. Notice that in the Theorem 1 on p2, it is mentioned that the result you state implies the hardness of the strong edge coloring. On p5, it is told that the strong chromatic index $\chi'_S(G)$ is equal to ...


2

A decision procedure for an NP-complete problem need not find a solution. As an example, one decision procedure for 3-SAT is to count the number of assignments explicitly excluded by the CNF clauses. Care has to be taken not to double-count assignments excluded by more than one clause. If the total number of assignments excluded is less than $2^n$ (where ...


3

The doubly exponential worse case runtime for deciding Presburger arithmetic theorems occurs only when nested quantifiers are used. Since the paper describes a quantifier-free version of Presburger arithmetic, the doubly exponential lower bound does not apply. We're left with the singly-exponential runtime upper-bound known for all NP-complete problems and ...


1

Hint: The power $j$ on $n^j$ in the denominator stays the same, but your power on the logarithm drops by $1$. What happens if you do this over and over so that the power on $\log$ becomes less than or equal to zero? Then you can put it in the denominator by switching signs on the power and hopefully be able to determine the limit from there, assuming $j > ...



Top 50 recent answers are included