Tag: problem

Can the following problem be reduced to each other to show that the satisfiability of the given boolean formular is NP hard?

Inspired by this problem: MIN-2-XOR-SAT and MAX-2-XOR-SAT: are they NP-hard?

I am interested to know whether or not if the satisfiability check of the following boolean expression is also NP-hard:

$ \bigwedge_{a\in V}\left(\bigvee_{b\in N[a]}(x_a\veebar x_b)\right)$

In the formula above $ V$ are formulas, $ N[a]$ is the set of neighbours of $ a$ a node from $ V$ . $ x\in\{0,1\}$ the formula above is satisfied when each node of type $ 0$ is adjacent to atleast one node of type $ 1$ and vice versa.

Minimizing the distance using a subtree problem

We have a binary tree with n nodes and a number k which signifies the number of nodes on a subtree. What is the optimal algorithm to select a subtree consisting of k nodes, that minimizes the maximum distance of a node (of our tree) from an ancestor of his that belongs in the subtree we have chosen. By distance we mean the steps we have to take to get to the ancestor, if every edge has a cost of 1. For this problem we always have to take the root of the binary tree to belong in the subtree.

I have figured out, that I have to use Dynamic Programming to solve this problem, but I can’t find the recursive function. I also think, to optimize the complexity, the recursive function should start from the bottom of the tree, to work its way on the top.

Smoothed analysis of the Partition problem

I am studying smoothed analysis and trying to apply it to the Partition decision problem: given $ n$ real numbers with a sum of $ 2 S$ , decide whether there exists a subset with a sum of exactly $ S$ .

The common definition of the smoothed runtime complexity of an algorithm is: given $ n$ and $ \sigma$ , the smoothed runtime of an algorithm is the maximum, over all inputs of size $ n$ , of the runtime on the input when it is perturbed by a perturbation of size $ \sigma$ , e.g. by adding to each input a number selected randomly from a normal distribution with standard deviation $ \sigma$ , or from any distribution with support $ [0,\sigma]$ .

If I apply this definition to the Partition problem, it seems that for any $ \sigma > 0$ , the runtime complexity is $ O(1)$ , since for any random noise that is added to the original numbers – no matter how small – the answer is “no” with probability 1.

This is strange, since in the more common examples of smoothed analysis, the runtime complexity depends on $ \sigma$ , and here it does not.

Is there something I misunderstood? What is the smoothed runtime complexity of Partition?

Using undecidability of the halting problem to show that the function also calls recursively in $2i$ if $i$ halts

Let $ \{P_i|i = 1, 2, . . .\}$ be list of all computable functions. For example, $ P_i$ might be the $ i$ th program and $ P_i(x)$ would be the output given by that program on input $ x$ .

Suppose that there is an algorithm to decide whether or not a given procedure calls itself.

Consider the procedure $ FUNC(x)$ :

PROCEDURE FUNC (INTEGER X);       BEGIN INTEGER 1, J;       I ← X DIV 2;       J ← X MOD 2;       IF J = 0 AND Pi(i) halts THEN FUNC (X + l); END

How do I use Undecidability to show that $ FUNC(2 ∗ i)$ calls $ FUNC$ recursively if and only if $ P_i(i)$ halts?

Prove the Droid Trader Problem is NP-complete

This question is from Algorithms Design.

A player in the game controls a spaceship and is trying to make money buying and selling droids on different planets. There are $ n$ different types of droids and $ k$ different planets. Each planet $ p$ has the following properties: there are $ s(j, p) \geq 0$ droids of type $ j$ available for sale, at a fixed price of $ x(j, p) \geq 0$ each, for $ j = 1, 2, \dots , n$ , and there is a demand for $ d(j, p) \geq 0$ droids of type $ j$ , at a fixed price of $ y(j, p) \geq 0$ each. (We will assume that a planet does not simultaneously have both a positive supply and a positive demand for a single type of droid; so for each $ j$ , at least one of $ s(j, p)$ or $ d(j, p)$ is equal to $ 0$ .)

The player begins on planet $ s$ with $ z$ units of money and must end at planet $ t$ ; there is a directed acyclic graph $ G$ on the set of planets, such that s-t paths in $ G$ correspond to valid routes by the player. (G is chosen to be acyclic to prevent arbitrarily long games.) For a given s-t path $ P$ in $ G$ , the player can engage in transactions as follows. Whenever the player arrives at a planet $ p$ on the path $ P$ , she can buy up to $ s(j, p)$ droids of type $ j$ for $ x(j, p)$ units of money each (provided she has sufficient money on hand) and/or sell up to $ d(j, p)$ droids of type $ j$ for $ y(j, p)$ units of money (so I’m assuming you can make multiple buy/sells at each planet). The player’s final score is the total amount of money she has on hand when she arrives at planet $ t$ .

I’m trying to prove this problem is harder than some NP-complete problem, but I am quite stuck. Since the planets are organized in a DAG, I think the ‘hardness’ of the problem comes from the fact that you can buy and sell many different types of droids at each planet. Also, this problem is a maximation problem, and I don’t know many NP-complete maximization problems other than quadratic assignment.

Can I get a hint on how to do this? Such as what problem X should I choose to reduce to Droid Trader Problem. Thanks!

Git Merge Lowest common ancestor problem

How does Git find the ‘merge base’ of two branches in a commit graph? From what I understand, this reduces to finding the lowest common ancestor of a directed acyclic graph. After reading up on several algorithms with which one may do this, I am wondering how Git manages to solve the LCA problem.

(Apologies if this is more of a stack overflow question. I am however more interested in the internal algorithm Git uses so it may be appropriate for this forum.)

How to prove LastToken problem is NP-complete

Consider the following game played on a graph $ G$ where each node can hold an arbitrary number of tokens. A move consists of removing two tokens from one node (that has at least two tokens) and adding one token to some neighboring node. The LastToken problem asks whether, given a graph $ G$ and an initial number of tokens $ t(v) \ge 0$ for each vertex $ v$ , there is a sequence of moves that results in only one token being left in $ G$ . Prove that LastToken is NP-complete.

I’m learning how to prove NP-complete recently but having trouble to understand the concept of NP. As far as I know, to prove a problem is NP-complete, we first need to prove it’s in NP and choose a NP-complete problem that can be reduced from. I’m stuck on which NP-complete problem that can reduce to my problem. As I interpreted this is sequencing problem and I’m guessing I can either reduce Ham Cycle or Traveling Sales Man to my problem, but I don’t see any connection between them so far. How should I start a good approach?

Alfa wireless card monitor mode problem [closed]

enter image description hereI have a wireless card (Alfa AWUS036H) that I use for pen-testing on my test network. Due to my recent interest in network hacking, I picked up this card and put it into monitor mode. While it scanned networks fine and picked up strong signals from neighboring networks, if I disconnected it or restarted my computer the next day, it would not discover any networks using the command airodump-ng wlan0mon wlan0mon being the interface of the card.

To get the card to work again, I would have to restart the virtual box, unplug the device or even restart my computer multiple times to get it to work. I don’t know if it is a software problem or a hardware issue. If this was a real-world situation this would in no way be practical.

I run kali-linux 2019.1 on virtual-box 5.2. My computer runs on Windows 10.

Your help would be appreciated.

Dynamic length of union of segments (1d Klee’s measure problem)

Finding the length of union of segments (1-dimensional Klee’s measure problem) is a well-known algorithmic problem. Given a set of $ n$ intervals on the real line, the task is to find the length of their union. There is a simple $ O(n \log n)$ solution involving sorting endpoints of all intervals and then iterating over them while keeping track of some counters.

Now let’s look at a dynamic variant of this problem: we are receiving $ n$ segments one after another and the task is to find the length of the current union of segments after each new segment arrives. It seems like a natural generalization, however, I cannot find much information about this version of the problem. I wonder if it is still possible to solve this problem in $ O(n \log n)$ time in an offline setting, i.e. when we are given all segments beforehand and can preprocess them in some way before giving an answer for each segment.

I feel like a modification of a segment tree might be useful here. In every node we need to keep track of both the total sum of lengths of segments (or their parts) corresponding to this node and the length of their union. However, I cannot figure out how to implement this modification without performance of one update degrading to linear time in some cases. Maybe using a segment tree is not the right approach and a better way exists.