# Questions tagged [np]

NP ("nondeterministic polynomial") is a complexity class of decision problems that can be solved by a nondeterministic Turing machine in polynomial time. Equivalently, it is the set of decision problems for which an answer can be verified in polynomial time by a deterministic Turing machine.

**0**

votes

**0**answers

13 views

### Exception has occurred: ValueError all the input arrays must have same number of dimensions

What I'm trying to do is take a 250 x 250 px image and turn all the text onto it to 1s and the rest to 0s, then pass this through a neural network. To turn the image to 1s and 0s, I wrote this ...

**-1**

votes

**1**answer

51 views

### Np class of problems

Are All problems in NP are known to be reducible to one another.
I know if a problem X is in NP and any NP problem Y in NP is reducible to X then X is NP-complete. So by this assumption can we state ...

**0**

votes

**0**answers

20 views

### Cook's theorem and NP complete reductions

Based on Cook's theorem,
Any NP problem can be converted to SAT in polynomial time
I know that SAT is a NP-complete problem. Therefore, is it accurate to say:
If we can reduce a search problem A (...

**0**

votes

**1**answer

28 views

### Having trouble understanding the MAX-CUT problem

I'm having trouble understanding the general idea behind the MAX-CUT problem. Consider the graph below.
The MAX-CUT asks us to find the cut that maximizes the number of edges that it touches. I can ...

**-1**

votes

**0**answers

13 views

### Maximum Independent Set to Max SAT

Given a graph G=(V, E) how can you transform it into CNF, in-order to find the Maximum Independent Set using a Max SAT solver?

**1**

vote

**1**answer

50 views

### What approximate TSP algorithm does Google OR-Tools use?

I came across Google OR-Tools which computes the TSP with reasonable approximations as discussed in this link. I am curious to know what specfic algorithm this tool uses for TSP. Does it have any ...

**-1**

votes

**0**answers

11 views

### How to get general response header values in nodejs

Hi I wanna get the value of general response headers of any site when it loads like the following picture shows
How Can I Get Its Value in NodeJs?

**3**

votes

**3**answers

62 views

### If these problems are NP-Complete, how are there polynomial time algorithms for solving them?

I'm studying P, NP, and NP-Complete problems and I've encountered some questions.
I understand that a problem is P if you can solve it in polynomial time, and a problem is NP if it is verifiable in ...

**0**

votes

**2**answers

44 views

### Merge k unsorted lists into one and sort them and then separate them into k sorted lists?

Say I have k unsorted list and I want to merge them into one list so that I could run my sorting algorithm on them, and then I need to separate this large merged list to get k sorted list. How could I ...

**0**

votes

**0**answers

7 views

### If we can prove that knapsack problem with limited capacity are solved in a polynomial time then all knapsack belongs to P

I found this question in my Optimization Algorithm course, the full question is this:
If we can prove all Knapsack problems with capacity limited to 100 can be solved in polynomial time, then all ...

**0**

votes

**1**answer

24 views

### What is the difference between my own hot_labels and creating hotlabels with functions?

I am new to python and machine learning, since I have been learning day by day. I want to clear somethings, and this time about my labels. I have 2004 classes to classify from. And I am building ...

**-2**

votes

**1**answer

50 views

### What is the best algorithm for travelling sales man problem in case of there is few cites(lower than 6)? [closed]

i have seen many solution that try to solve the problem of travelling salesman problem if p!=np ,but i want to know the optimum solution if there is 6 or 5 cities only,which algorithm will give the ...

**0**

votes

**1**answer

149 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

**1**answer

122 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

**1**answer

46 views

### Can someone give me an example for longest path problem having a NP complexity?

I saw on the internet that finding the longest path problem is NP-Complete problem.
For some reason, my teacher tells me that it isn't an NP-complete problem.
So now I am looking for an example that ...

**0**

votes

**0**answers

38 views

### Given a set of intervals on the number line, find the minimum points that “cover” all the intervals (optimium solution efficiently)?

I've been trying to find an efficient way to solve this problem of finding "minimum" (not minimal) time points, but not sure if it's that straightforward. I tried modeling it as a minimum edge cover ...

**-3**

votes

**1**answer

42 views

### Priority interval scheduling algorithm

I have the following problem.
Imagine a set of jobs, with start time (st) and end time (et). Each job has a priority value. I need to schedule these jobs using a number of machines greater than 1.
...

**0**

votes

**2**answers

67 views

### Algorithm Problem: Find the longest elementary cycle in a directed graph

The problem is: given a directed graph, find the longest simple cycle in the graph. I've searched the question and found this link Finding the longest cycle in a directed graph using DFS. The answer ...

**0**

votes

**1**answer

15 views

### Proof the longest path is NP-Hard with negative edge weights

I know a similar question has been asked before and that there are abundant amount of resources online, but I have a slightly different question. I understand the reduction from HAM Path to Longest ...

**0**

votes

**1**answer

53 views

### What optimization algorithm is more suitable for timetable rescheduling?

I'm working on the project where university course is represented as a to-do list, where:
course owner (teacher of the course) can add tasks (containing the URL to the resource needs to be learned ...

**0**

votes

**0**answers

29 views

### Speed up N(P) problem search - Sum-Square Problem

Speed up N(P) problem search - Sum-Square Problem
I was wondering if anyone could help me figuring out ways to speed up a small programm I was working on.
The problem is a math exercise called the ...

**0**

votes

**1**answer

123 views

### Prove a problem that is NP-hard and not NP-complete in not in P

If A is not NP-hard, but not NP-complete, then prove that A in not in P.
A is NP-hard if there is an NP-complete problem B such that B is reducible to A in polynomial time. A is NP-complete if A ...

**2**

votes

**1**answer

59 views

### I understand 2 SAT can be solved in Polynomial time finding out Strongly Connected Components. What about doing the same for 3SAT?

In case of 3SAT instead of getting 2 implications for one clause, we'd get 12(3C2*2*2) maybe.and which will form a graph of 12m edges when m is the number of clauses in 3 CNF and we can still find out ...

**0**

votes

**0**answers

38 views

### RuntimeWarning: invalid value encountered in double_scalars when solving system of equations

I know this is a recurrent question, but I cannot find the mistake in my code that is generating this error.
I want to solve a system of equations of the following form
System of equations
When I ...

**0**

votes

**0**answers

30 views

### NP-completeness/Reduce from SAT to 3SAT

I have a problem concerning the proof of NP-completeness of k-SAT. I must convert the formula Q = (x v p) ∧ (-x v y v z v -p) ∧ (-y v q v -z) into 3-SAT. I have done that as follow;
Q' = (x v p v y1) ...

**0**

votes

**0**answers

36 views

### TSP-OPTIMIZE is NP equivalent or strictly NP hard? Looking for a good citation

I'm wondering whether TSP-OPTIMIZE is NP-equivalent, like the proof wiki claims or if it is strictly NP-hard. To clarify, I'm talking about the optimization problem, that is to find the shortest round ...

**-1**

votes

**1**answer

44 views

### Why is the performance of the same loop algorithm differs

Right now I am doing assignments from cs 231 n , and I wanted to calculate euclidean distance between points:
dists[i, j]=0
for k in range(3072):
dists[i, j]+=math.pow((X[i,k] - self.X_train[j,k])...

**0**

votes

**1**answer

60 views

### Issue with creating a column using np.where, ArrayType error

I have a dataframe in which I'm trying to create a binary 1/0 column when certain conditions are met. The code I'm using is as follows:
sd_threshold = 5
df1["signal"] = np.where(np.logical_and(df1["...

**0**

votes

**0**answers

30 views

### Finding reduction to prove that a language is NP-complete

I need to prove that the following problem is NP-complete:
We have n diplomats from n countries and we need to seat them around a round table.
We also get a list of diplomats who don't get along with ...

**-1**

votes

**1**answer

44 views

### NP, NP-Complete, NP-Hard questions

I am studying NP and I can't understand how can I solve the below questions. I would like to know the strategy that I should use to be able to solve this kind of problems.
The question is:
Assume A ...

**0**

votes

**0**answers

76 views

### Algorithm to avoid obvious costly combinations when splitting n values to m groups

I have 7 values and I need to split them into 5 groups. Each group should contain atleast one value. There are 15 ways to group those values into 5.
Mon- 13
Tue- 5
Wed- 4
Thu- 4
Fri- 11
Sat- 2
Sun- ...

**0**

votes

**1**answer

93 views

### optimal algorithm to solve CLSP(Capacitated Lot Sizing) with the transportation constraints and storage levels

A bank has an ATM machine. For a particular week, the usage of cash in millions as below.
5- Monday
4- Tuesday
1- Wednesday
15- Thursday
6- Friday
2- Saturday
4- Sunday
The bank hires a depositing ...

**0**

votes

**1**answer

23 views

### In complexity class P, accepts=decides. Why not NP?

Suppose some problem L is in the complexity class P. Then there is some polynomial time algorithm A that decides the problem. We have the following theorem: if A accepts L, then A decides L.
The ...

**0**

votes

**0**answers

34 views

### Accepting a Language Vs Rejecting a language

I have a question on complexity theory. I have the following definition in my notes:
If algorithm A is such that A(s) halts with output 1 for all s in language L, then A accepts L.
My question is,...

**0**

votes

**0**answers

16 views

### Finding the best combination of Timeslots in a set

I have the following problem:
I want to find 3 Timeslots in a week that are both:
"nicely distributed" and "have a good quality"
Timeslots are always 1 hour long, so each day of the week has 24 ...

**0**

votes

**1**answer

284 views

### Example in np.argsort document

For some reason I cannot resolve this.
According to the example here for 1-dim array,
https://docs.scipy.org/doc/numpy/reference/generated/numpy.argsort.html
x = np.array([3, 1, 2])
np.argsort(x)
...

**1**

vote

**1**answer

25 views

### NP or Not? Finding a word in an existing dictionary surrounded by Gibberish

So a friend and I have a question which we can't find an answer to.
Given a String of unknown length or size covered in gibberish note the word CAN be misspelled by one or two charachters. Is it ...

**1**

vote

**0**answers

64 views

### Is finding all primes less than n, doable in polynomial time?

Bear in mind I'm almost a complete noob at complexity theory.
I was reading about how AKS Primality shows that numbers of size n can be shown to be prime or composite in polynomial time. Given that, ...

**2**

votes

**0**answers

45 views

### Parallel estimation of multiple nonparametric models using np and snowfall

I am trying to estimate multiple nonparametric models using snowfall. So far I had no problems, but now I run into a problem that I feel unable to resolve.
In the MWE below we simply estimate only ...

**1**

vote

**1**answer

41 views

### What does the word “amortized” mean in amortized analysis of algorithms? [closed]

I obviously am familiar with the texts mentioning it is an average lower bound etc... but still wondering why the word amortized was put there ?
Why is amortize used in describing algorithm analysis ?...

**1**

vote

**1**answer

41 views

### NP to P transition

Are there any recent (feel free to add the "old" ones too) problems that were perceived as NP and then later someone came up with a solution that is Polynomial? I think studying those cases would ...

**0**

votes

**0**answers

26 views

### Reduction from Vertex Cover to Restricted LP

The Restricted LP Problem is as follows:
Given a nn matrix A, a vector b in R^n, and a positive integer k. Does there exists a vector x in R^n with at most k non-zero entries such that Ax is greater ...

**0**

votes

**0**answers

28 views

### Proving NP-completeness of 2 independent paths in graph

So here is a problem:
Given directed and weighted graph G and two of its vertices a and
b, we want to find two vertex-independent paths from a to b with sum of weights less than given number n.
...

**0**

votes

**1**answer

37 views

### Does Reducing P or NP instance to NP-Complete make that instance also NP-Hard?

If a Problem X lying in P or NP can be reduced to NP-Complete, is that problem X automatically an NP-Hard problem?

**0**

votes

**1**answer

111 views

### np.loadtxt giving ValueError: could not convert string to float: b'2017-07-26'

Saw couple of responses with the above mentioned error but culdn't figure out bug in my code. I am following tutorial at: https://pythonprogramming.net/unix-time-matplotlib-tutorial/?completed=/basic-...

**1**

vote

**1**answer

72 views

### N Queen with predefined queen(s)

The origin N-Queen problem is about placing N Queens on a N*N board.
However, I have been questioned from one of my academic friends:
Is there any NP-completeness proof for the N Queen problem with ...

**21**

votes

**4**answers

3k views

### How to test an `npm publish` result, without actually publishing to NPM?

One common problem I have, is that sometimes my .npmignore file is too aggressive, and I ignore files that I actually will to include in the NPM tarball.
My question is - is there a way to test the ...

**0**

votes

**0**answers

14 views

### Optimization-Polynomial Algorithm

I know there is no known algorithm that solves this problem in polynomial time. But how to prove that an optimization had no known polynomial algorithm?

**-1**

votes

**1**answer

29 views

### Why is A _< B always true in a Polynomial Reduction?

I'm extremely knew to Computer Science, particularly the theoretical side, so am trying to understand (without an answer going too far over my head) why is always true in a polynomial time reduction, ...

**-1**

votes

**1**answer

36 views

### Construct a ciruct from a graph that outputs 1 if the graph has an independent set

Let's say I have a graph,
and from this graph I want to create a circuit K whose inputs can be set so that K outputs true iff the graph has an independent set of size ≥2.
I've seen some decent stuff ...