title: concurrency in multiple core

text:
# Question
Title: concurrency in multiple core
I know the basic definition between parallelism and concurrency. But there is not much information about concurrency in multiple core.

what is the difference between concurrency in single-core vs concurrency in multiple-core?

Is there much difference **performance-wise** between concurrency in multiple core vs parallelism in multiple core?

# Answer
Modern multi-core processors are parallel.

First I want to explain why a single core processor (no hyper threading) offers instruction-level parallelism.

First they have pipelined-parallelism, so they have multiple instructions from a single instruction stream at various stages in the pipeline. So in the typical cs literature you will see the 5 stages of a RISC processor:

* fetch
* decode
* execute
* memory access
* write back (write changes to memory/registers).

But modern processors have many more stages. Modern Intel processors have between 16-20 stages and older ones even had more.

Another dimension of instruction-level parallelism is super scalar execution. A processor has a few hundred instructions in its scheduling window (ROB) and it will execute instructions out of order as long as the input dependencies of the instructions are met (look for Tomasulo algorithm). So if there are a set of instructions that are independent of each other, these can be execute in parallel on different execution units. E.g. a Skylake has 4 ALU's and these can be run truly in parallel. So if a single add takes 1 clock cycle, in a single clock cycle you could do 4 adds.

Apart from instruction-level parallelism, there is thread-level parallelism: so parallelism due to having multiple instruction streams as you can see on SMT and SMP systems.

The nice thing about SMT that the CPU has multiple instruction streams to pick instructions from; so there is a greater chance that instructions can run in parallel based on functionality I explained above.

And the last one is SMP where there are multiple CPUs in a single package (aka multicore)
> 1 votes

# Answer
Concurrency is not parallelism: indeed, concurrency refers to the sharing of resources in the same time frame. As an example, several processes may share the same CPU or share memory or an I/O device.

Two processes (or threads) can be defined concurrent if an only if the second process starts execution before the first has terminated (assuming that the execution happens on the same core of a multi-core CPU).

Therefore, if the two processes both run on the same core of a multi-core CPU the processes are concurrent but not parallel: in this case, parallelism is only virtual and refers to the OS doing timesharing. The OS seems to be executing several processes simultaneously. But, since the processes execute on the same core, only one instruction from one process can be executing at any particular time. Since the human time scale is billions of times slower than that of modern computers, the OS can rapidly switch between processes to give the appearance of several processes executing at the same time.

If you instead run the two processes on two different CPUS, the processes are parallel: there is no sharing in the same time frame, because each process runs on its own CPU. The parallelism in this case is not virtual but physical.

Finally, it is worth noting here that two processes running on different cores of the same multi-core CPU can not be classified as fully parallel, because the processes share the same CPU caches and will even contend for them.

It should now be clear that performance-wise, parallelism is better than concurrency.
> 0 votes

---
Tags: operating-systems, parallel-computing, concurrency, threads
---


title: Mutual Friends in a Network?

text:
# Question
Title: Mutual Friends in a Network?
I always seem to have trouble finding a formal way to analyze this (be through proofs or whatever).

The problem statement is as such:

If A and B are friends, and B and C are friends, then A and C are friends too.

In a simple network like the following, this makes complete sense:

1 --- 2 --- 3

Analysis: We can see that 1 and 2 are friends, and 2 and 3 are friends. It follows from the problem statement that 1 and 3 must be friends too. This is the most generic case for a problem like this.

Where I get confused is in a following network:

1 --- 2 --- 3 --- 4

Analysis: We can see that 1 and 2 are friends, and 2 and 3 are friends; therefore, 1 and 3 must be friends. Also, since 2 and 3 are friends, and 3 and 4 are friends; therefore, 2 and 4 must also be friends.

Since 1 and 2 are already friends, would it follow from our conclusion of the last sentence (that 2 and 4 are friends) that 1 and 4 must also be friends?

Moving forward into a bigger picture, any group of connected nodes would also all be friends?

What's the best way to analyze this?

# Answer
> 1 votes
This is a possible way you can describe it:

Define $P$ to be the set of all possible people. Then, define the relation $F\subseteq P\times P$ such that $xFy$ (or equivalently, $(x,y)\in F$) only if $x$ is a friend of $y$.

Then, the requirements you stated are translated into the relation as follows:

1. Symmetric: If $x$ is a friend of $y$ then also $y$ is a friend of $x$. Formally, this is written as $$\forall x,y:xFy\iff yFx$$
2. Transitive: If $x$ is a friend of $y$, and $y$ is a friend of $z$ then $x$ is a friend of $z$. Formally, this is written as $$\forall x,y,z:(xFy\land yFz)\implies xFz$$
3. This one actually depends on whether you consider a person to be a friend with himself. If you restrict it such that every person is "a friend with himself", then the relation is also reflexive. Formally, this means that:$$\forall x:xFx$$

The combination of the above 3 properties is known as an equivalence relation. In such an equivalence relation, it is possible to "divide" the set $P$ into disjoint subsets $C\_1,\dots,C\_k$ such that all people in $C\_i$ are friends of all other people in $C\_i$, but aren't friends of any people in $C\_j$ for $j\neq i$. Those $C\_i$'s, are known as equivalence classes, and are known to be unique as well.

In your two examples, the subsets would simply be the entire population, hence any two people will be friends.

On the larger scale, if $x\_1$ is a friend of $x\_2$ which is a friend of $x\_3$ and so on until $x\_n$ for some $n\in\mathbb{N}$, then all of those $x\_i$'s will have to be in the same equivalence class, and hence will all be friends of each other.

# Answer
> 0 votes
You're probably looking for strong and weak ties, and specifically **strong triadic closure.**

In this framework, your graphs have two kinds of edges, strong and weak.

As you say, you shouldn't have an induced $P\_3$ if the two edges are strong. In that case, the edge 1-3 should exist, either as a weak edge of a strong edge.

You are, however, allowed to have an induced $P\_3$ provided that at least one of the edges are weak.

In the last case, with your $P\_4$, you need the edge 1-4 of and only if all edges are strong.

# Answer
> 0 votes
If you don't want to apply the framework of weak and strong links, you are probably looking for the concept \**transitive closure.

Yes, all pairs 1-2, 2-3, 3-4, 1-3, 2-4, as well as 1-4 will be friends in the transitive closure.

---
Tags: proof-techniques, neural-networks, computer-networks, network-topology, social-networks
---


title: Why this problem is NP-Hard?

text:
# Question
Title: Why this problem is NP-Hard?
I'm asking about the question described here: Knapsack Problem with exact required item number constraint

Can't we iterate over $\binom{n}{L}$ options (which is polynomial), and for each option check if the constraints are met?

# Answer
> 2 votes
$L$ is given as part of the input, and can be e.g., $n/2$, where $n$ is the number of items. Then, iterating over ${n\choose L}={n\choose \frac{n}2}$ is exponential.

Note that it doesn't matter whether $L$ is given in unary or binary, since $n$ is given in unary (as a list of the different items).

---
Tags: complexity-theory, np-complete, np-hard, np
---


# Question
Title: In what stage is next PC address available or known to the processor?
Assuming you know the meaning of pipelining in Computer architecture & organization. **When is the next PC address or jump address available or known to the processor?**

In this lecture, https://youtu.be/TMpjvAvQCWA?t=2346

Jump and branch addresses are computed during EXE or execution stage and are good to go ahead but I can't quite seem to understand why?

This concept is quite not available on websites out there and therefore, my apologies if wrong terms used here.

Thanks in advance.

# Answer
You can start with a simplified mental model: There is a program counter. The processor reads the instruction pointed to by the program counter, executes it, calculates the start of the next instruction to be executed, stores it into the program counter, and we start all over.

There are cases when the "next instruction" isn't stored after the previous instruction; when we have a branch instruction, or a conditional branch instruction (where we have two possible locations for the next instruction), and there are subroutine calls, where the processor needs to store the address of this or the next instruction in order to return. Just to make it more complicated.

In a simple pipelined processor, we'd want to read the next instruction as quickly as possible after reading the previous instruction. So the chip designers will do the utmost to make sure that the address of the next instruction is known in the next cycle, if at all possible. That involves determining the length of the current instruction as quickly as possible, checking that it is a branch instruction as quick as possible, and in case of a conditional branch either determine or guess the location of the next instruction as quick as possible. So in one cycle you would try to read the instruction, determine its length, and determine that it is a branch, so the program counter is known in the next cycle if at all possible.

In today's multi-issue processors, the processor will decode several consecutive instructions in the same cycle. Some instructions are complicated and their length may be hard to determine, and only one such instruction can be handled in a cycle. But other times you might have four very simple instructions in a row, and the processor can start executing all four of them, calculating only the program counter after executing the fourth instruction. The address of the 2nd, 3rd and 4th instruction might never make it into the program counter.

And then there are processors which translate instructions into RISC instructions. Such a processor may *rarely* know the program counter, but be able to determine the program counter if needed.
> 2 votes

# Answer
Today's processors work very differently. I.e., current Intel ones translate the CISC instrunction into a sequence of internal RISC instructions, which are scheduled on the fly to execute on the multiple internal functional units using the internal register files that shadow the programmer visible ones.

In any case, the address(es) for the next PC are available as soon as they are read or computed. If it is an absolute jump, it is part of the instruction, indirect jumps of any sort require further analysis/processing. Some processors even speculatively execute one or both branches of a conditional jump before deciding which way to go, discarding the one that doesn't pan out.

Most textbooks discuss technology as it was some decades ago, and then simplify/organize the material (reality is much messier than theory). Remember that literally hundreds, if not thousands, of engineer-years went into the design of current chips. You just can't compress all that into a few weeks of class time.
> 4 votes

---
Tags: computer-architecture
---


# Question
Title: Understanding the complexity class of a problem formulation
I'll keep the reasoning abstract. If I start from a mathematical formulation of a problem $A$ known to be $NP$-hard, I add a set of constraints which creates a problem $A'$.

However, I do know that there exists some instance of the problem for which the new set of constraint is empty, which brings, for those instance, back to the $NP$-hard formulation.

Is this enough to state that $A'$ is $NP$-hard?

# Answer
No (unless $P=NP$), here is a counter-example:

Consider $A:=SAT$. It is well known that this is an NP-complete problem (and hence also an NP-hard problem).

Now, we will add the following constraint: "every $\phi$ with length bigger than $100$ has to have at most $2$ variables in each clause".

For formulas with length less than $100$ the constraint doesn't apply, hence the condition you stated holds.

However, the resulting language is in $P$, since we can reduce it to $2SAT$ which is known to be solved in polynomial time. To do the reduction, simply "brute force" the answer for formulas $\phi$ with length less than $100$, and otherwise keep the formula as-is.
> 1 votes

---
Tags: np-hard
---


title: Why do Karnaugh maps work?

text:
# Question
Title: Why do Karnaugh maps work?
The question is quite straightforward: Why do Karnaugh maps work? What was the reasoning that led Maurice Karnaugh to come up with these maps? At first glance, it doesn't seem a natural approach, instead it feels somewhat arbitrary yet surprising that it works.

# Answer
The key here is **graycode**. I think the easiest way to see why Karnaugh maps work is to go through an example: Consider the following truth table:

$\hskip2in$

We can easily find the logical formula describing this table in terms of the sum of products formula (I will use the boolean algebraic notation): $$ \begin{align\*} E(A, B, C) &= \overline{A} \cdot B\cdot \overline{C} + A \cdot \overline{B}\cdot \overline{C} \+ A \cdot \overline{B}\cdot C+A\cdot B \cdot \overline{C} \\\&= B \cdot \overline{C}\cdot (\overline{A} + A) + A\cdot \overline{B}\cdot (\overline{C} + C)\\ &= B\cdot \overline{C} + A\cdot \overline{B} .\end{align\*} $$ Notice that when using the distributive law backwards, we always need two of the three variables to be constant and only one of the three to change and that it always simplifies if two stay constant and the third changes. The corresponding Karnaugh-map would look like:

$\quad\quad\quad\quad $

The alignment of the map entries exhibit a gray code alignment of the logical expressions, meaning that each entry's binary expression only differs by a single bit, e.g. first entry is $000$ and second entry is $010$ so they only differ in the second bit. This is exactly what we have found when examining the minimisation of the *Sums of products* representation, namely that we hold two values constant and consider the third one changing.

To read off the *Sum of products* representation of our logic table from the Karnaugh-map, we therefore first circle all the pairs of ones. For the light-green pair we find that $B$ and $C$ stay constant but $A$ changes making the $A$ term obsolete and, hence, obtain $B\overline{C}$. For the darker green pair we find that $A$ and $B$ stay constant but $C$ changes, leaving use with $A\overline{B}$. The last term follows analogously and you end up with the same formula found before.

I hope this makes the underlying concept clear, if you want me to further explain the generalised version of this, just tell me.
> 3 votes

---
Tags: boolean-algebra, karnaugh-map
---


# Question
Title: How to determine the approximation factor for greedy vertex cover algorithm?
The algorithm iteratively picks the vertex with maximum degree and removes it and every incident edge of the vertex, until only vertices with degree of $0$ are left.

Formally:

$\text{GreedyVertexCover}(G)$:

$C\leftarrow \emptyset$

**While** $(E\neq\emptyset)$

$\hspace{10pt}\text{Pick a vertex }v \text{ that has maximum degree}$

$\hspace{10pt}C\leftarrow C\cup \\{v\\}$

$\hspace{10pt}E=E\setminus\\{e\in E:v\in e\\}$

$\hspace{10pt}\text{Remove all vertices with degree 0}$

$\text{ Return } C$

My idea of the upper bound (please correct me if wrong): let $v\_1, ..., v\_n$ be the removed vertices. Define the cost of removing a vertex $v\_i$ to be $c(v\_i) = \cfrac{1}{\deg(v\_i)}$. At any iteration $i$, among the vertices of the complementary set $\bar{C}$, there must exists a vertex with cost of at most $\cfrac{OPT}{n - i + 1}$. Therefore the cost of constructing the set $C$ can be at most

$$\sum\_{i = 1}^{n} \cfrac{OPT}{n - i + 1} = \mathcal{O}(\log n) \cdot OPT $$

# Answer
> 3 votes
The approximation factor can be $\Omega(\log n)$.

Consider a bipartite graph $G$ with a set $S\_L$ with $n$ nodes on the left side. Also consider a collection of sets $S\_{R,1},S\_{R,2},\dots,S\_{R,n}$ on the right side where each set $S\_{R,i}$ has an edge to $i$ vertices in $S\_{L}$ and no two vertices in $S\_{R,i}$s have common edge . So $\lfloor{\frac{n}{i}}\rfloor$ in it. So the sum of size of $S\_{R,i}$s $$\sum\_{i=0}^n |S\_{R,i}|=\Theta(n\log n).$$

After running GreedyVertexCover on this instance, it select all nodes on right side, but the optimal solution was to select all nodes in $S\_L$.

Consequently, $$\frac{ALG(G)}{OPT(G)}=\frac{n\log n}{n}=\log n.$$ So the approximation factor of your algorithm is $\Omega(\log n)$.

---
Tags: approximation, greedy-algorithms, vertex-cover
---


# Question
Title: Is a universal assembly language for all computers possible?
I would like to ask a few questions about Assembly language. My understanding is that it's very close to machine language, making it faster and more efficient.

Since we have different computer architectures that exist, does that mean I have to write different code in Assembly for different architectures? If so, why isn't Assembly, write once - run everywhere type of language? Wouldn't be easier to simply make it universal, so that you write it only once and can run it on virtually any machine with different configurations? (I think that it would be impossible, but I would like to have some concrete, in-depth answers)

Some people might say C is the language I'm looking for. I haven't used C before but I think it's still a high-level language, although probably faster than Java, for example. I might be wrong here.

# Answer
Assembly language is a way to write instructions for the computer's instruction set, in a way that's slightly more understandable to human programmers.

Different architectures have different instruction sets: the set of allowed instructions is different on each architecture. Therefore, you can't hope to have a write-once-run-everywhere assembly program. For instance, the set of instructions supported by x86 processors looks very different from the set of instructions supported by ARM processors. If you wrote an assembly program for an x86 processor, it'd have lots of instructions that are not supported on the ARM processor, and vice versa.

The core reason to use assembly language is that it allows very low-level control over your program, and to take advantage of all of the instructions of the processor: by customizing the program to take advantage of features that are unique to the particular processor it will run on, sometimes you can speed up the program. The write-once-run-everywhere philosophy is fundamentally at odds with that.
> 47 votes

# Answer
The DEFINITION of assembly language is that it is a language that can be translated directly to machine code. Each operation code in assembly language translates to exactly one operation on the target computer. (Well, it's a little more complicated than that: some assemblers automatically determine an "addressing mode" based on arguments to an op-code. But still, the principle is that one line of assembly translates to one machine-language instruction.)

You could, no doubt, invent a language that would look like assembly language but would be translated to different machine codes on different computers. But by definition, that wouldn't be assembly language. It would be a higher-level language that resembles assembly language.

Your question is a little like asking, "Is it possible to make a boat that doesn't float or have any other way to travel across water, but has wheels and a motor and can travel on land?" The answer would be that by definition, such a vehicle would not be a boat. It sounds more like a car.
> 13 votes

# Answer
There is no *conceptual* (I daresay, no computer *science*) reason against having one assembly language for all computers in the world. In fact, that would make many things much easier. As far as theory is concerned, they are all the same, anyway, up to some funky bijection.

In practice, however, there are different chips for different purposes, with different operations and design principles (e.g. RISC vs CISC) that serve different goals, and the instruction sets that operate them and therewith the assembly languages differ. In the end, the answer is the same as when asking why there are so many different programming languages: different goals, different design decisions.

That said, you can of course introduce levels of abstraction to get to some shared interface. x86, for instance, has been done away with on chip level for quite some time; there's a little piece of hardware that translates x86 instructions to whatever your processor *really* works with. Languages like C would be another step away from the hardware (if an arguably tiny one), all the way up to languages like Haskell, Java or Ruby. Yes, compiler are one of the main achievements of computer science because they make it possible to separate concerns in this fashion.
> 8 votes

# Answer
You mention the phrase "write once run anywhere" without seeming to notice its significance. That is the marketing slogan for Sun Microsystems that commercially invented the concept of a "virtual machine" and "bytecodes" for Java, although possibly the idea may have originated in academia 1st. The idea was later copied by Microsoft for .Net after they were successfully sued by Sun for breach of infringement of Java licensing. Java bytecodes are an implementation of the idea of cross-machine assembly or machine language. They are used for several other languages than Java and can theoretically be used to compile any language. After many years of very advanced optimization, Java comes close in performance to compiled languages showing the goal of high performance platform-agnostic virtual machine technology is achievable in general.

Another new idea in early stages/ circulating related to your requirements is called the recomputation project and is for scientific research although could be used for other purposes. The idea is to make computational experiments replicable via virtual machine technology. This is mainly the idea of simulating different machine architectures on arbitrary hardware.
> 7 votes

# Answer
## High level reasons

When you think about it, a microprocessor does an amazing thing: it lets you take a machine (such as a washing machine or an elevator), and replace a whole chunk of **custom-designed** mechanisms or circuits with a cheap, mass-produced silicon chip. You save a lot of money on parts, and a lot of time on design.

But hang on, a **standard** chip, replacing countless **custom** designs? There can't be a single, perfect microprocessor that is perfect for every application. Some applications need to minimise power usage but don't need to be fast; others need to be fast but don't need to be easy to program, others need to be low cost, etc.

So, we have many different "flavours" of microprocessor, each with its own strengths and weaknesses. It is desirable for them to all use a compatible instruction set, because this allows code reuse and makes it easier to find people with the right skills. However, the instruction set *does* affect the cost, complexity, speed, ease-of-use, and physical constraints of the processor, and so we have a compromise: there a few "mainstream" instruction sets (and many minor ones), and within each instruction set there are many processors with different characteristics.

Oh, and as technology changes, all these trade-offs change, so instruction sets evolve, new ones emerge, and old ones die. Even if there was a "best" instruction set of today, it might not be in 20 years.

## Hardware details

Probably the biggest design decision in an instruction set is the **word size**, i.e. how large a number the processor can "naturally" manipulate. 8-bit processors deal with numbers from 0-255, whereas 32-bit processors deal with numbers from 0 to 4,294,967,295. Code designed for one needs to be completely rethought for another.

It is not just a matter of translating instructions from one instruction set to another. A completely different approach may be preferable in a different instruction set. For example, on an 8-bit processor a lookup table may be ideal, while on a 32-bit processor an arithmetic operation would be better for the same purpose.

There are other major differences between instruction sets. Most instructions fall into four categories:

* Computation (Arithmetic and logic)
* Control Flow
* Data Transfer
* Processor configuration

Processors differ in what sort of computations they can perform, as well as how they approach control flow, data transfer, and processor configuration.

For example, some AVR processors can neither multiply nor divide; whereas all x86 processors can. As you may imagine, eliminating the circuitry required for tasks like multiplication and division can make a processor simpler and cheaper; these operations can still be performed using software routines if they are needed.

x86 allows arithmetic instructions to load their operands from memory and/or save their results to memory; ARM is a load-store architecture and thus only has a few dedicated instructions for accessing memory. Meanwhile x86 has dedicated conditional-branch instructions, while ARM allows practically *all* instructions to be conditionally executed. Also, ARM allows bit-shifts to be performed as part of most arithmetic instructions. These differences lead to different performance characteristics, differences in internal design and cost of the chips, and differences in programming techniques at the assembly language level.

## Conclusion

The reason it is impossible to have a universal assembly language is that, to properly convert assembly code from one instruction set to another, one must design the code all over again—something computers cannot yet do.
> 5 votes

# Answer
Adding to marvelous answer by D.W.: if you would like to have one assembler it would need to maintain all architectures, perfect translator among them and fully understand what are you doing.
Some heavily optimized codes per one architecture would need to be deoptimized, understood at more abstract level and optimized per another.
But if this was possible we would have perfect C compiler, and writting in pure assembly would not be beneficial at all.
The main point of using assembler is performance, which cannot be squeezed from recent compilers.
Writing such program would be even harder than existing compilers and maintaining all new architectures that are being created would make it even harder.
And for "one only" program, it would also mean full backwards compatibility.
> 4 votes

# Answer
As noted, LLVM is the closest thing to this so far. A big barrier to a really universal language is going to be fundamental differences related to implicit tradeoffs: concurrency, memory use, throughput, latency, and power consumption. If you write in an explicitly SIMD style, you could be using too much memory. If you write in an explicitly SISD style, you would get suboptimal parallelization. If you optimize for throughput, you hurt latency. If you maximize single-threaded throughput (ie: clock speed), you hurt battery life.

At the very least, the code would need to be annotated with the trade-offs. What may be most important is for the language to have good algebraic/type properties that give the compiler a lot of wiggle room to optimize and detect logical inconsistency.

Then there is the question of undefined behavior. Much of the speed of C and assembly languages come from undefined behavior. If you admit undefined behavior that actually does happen, then you end up handling them as special cases (ie: architecture and context specific hacks).
> 3 votes

# Answer
I'm going to go against every other answer posted so far; they were reasonable at the time, but are now somewhat obsolete. I posit that true answer is, in fact:

# It's totally possible, and some very big companies went ahead and did exactly that.

> WebAssembly (abbreviated Wasm) is a binary instruction format for a stack-based virtual machine. Wasm is designed as a portable target for compilation of high-level languages like C/C++/Rust, enabling deployment on the web for client and server applications.

In other words, WebAssembly is a bytecode format which is designed to be easy for C++-adjacent languages to compile into, while also being easy to run safely on your browser.

Now, one might argue that WebAssembly isn't an "universal assembly language". First, **it's not exactly assembly**, in the sense that no processor can run it as-is; its instructions have to be compiled to machine code first, usually with additional overhead in the form of safety checks. Second, **it's not inherently universal**, in that there are lots of architectures it can't be compiled to (GPUs and FPGAs come to mind).

In that regard, the other answers are still relevant: WebAssembly makes a bunch of trade-offs, sacrificing some performance for safety and portability. Writing WebAssembly and compiling it to regular assembly is always going to produce a less efficient program than directly writing assembly.

I'd still argue that it's pretty damn close on both criteria:

* **It's assembly-like**, in that it's a language with a lot of information baked-in. It doesn't care about type information, generics, casting, virtual dispatch, etc. It can only read from a write to a contiguous range of data called linear memory; and since it doesn't *know* how that memory is structured, it only needs to worry about preventing out-of-bounds accesses; **structuring reads and writes is the responsibility of the code being compiled into wasm**, much like with regular machine code. Thus, compiling from WebAssembly is a lot cheaper and faster than compiling from C++, which is why your browser can afford to ship with a wasm compiler.
* **It's universal-like**, in that it can be made to run on any machine that we'd expect C++ (and every other generalist programming language on the market) to run on. It uses very simple primitives, that match pretty closely to the physical architecture of most CPUs (RAM, registers, branching, etc).

There are other arguments for wasm adoptions (it's open-source, unlike Java bytecode, it's widely-supported, etc), but the two points above are the most relevant to your question.

**If what you're looking for is an extremely-low level code format, that can be compiled from most languages and run on most machines, then you want WebAssembly.**
> 1 votes

# Answer
Perhaps what you are looking for is a Universal Turning Machine notation where everyone agrees on the symbols for the commands. (https://en.wikipedia.org/wiki/Universal\_Turing\_machine)

An 'assembler' that translates a Turning Acceptable language to the underlying vendor specific machine code and be build for any of those things we call computers.

In The Art of Computer Programming the there is a example of what this might look like.

But consider the question "why isn't their a commercially available universal language that can be used with all computers" I'd suggest the most dominiant influances are (1) convenience, not all assembly languages are the most convienent to use; (2) economics, providing, incompatibility between machines of different brands and vendors is a business strategy as well as the result of limited resources (time/money) to design machines.
> 0 votes

# Answer
assumption: compiling and optimising a high-level language L1 to a lower-level language L0 is easier than compiling and optimising a high-level language L2 (higher than L1) to L0; easier in the sense that you supposedly can generate more optimised code when compiling L1 to L0 than L2 to L0.

I think the assumption is probably correct, that is why probably most compilers use a low-level intermediate language (IR/LLVM).

if this is true than use any low-level language L0 and write compilers to translate L0 to other low-level languages. For example, use MIPS instruction set, and compile it to x86, arm, power, ...

-Taoufik
> 0 votes

# Answer
A Universal Assembly Language? Of course. By default, you just endow the language with a giant switch table; if (x86) then ... if (68x00) then ... if (AMD) then ... and maybe factor out the stuff that's in common between CPUs, and provide a facility for plug-ins to add new CPUs.

Essentially, most or all of that is what GAS already does.

You can make a Universal Anything this way; even a Universal Universal (a universal language for universal languages).

The question can be better posed as this: are there universal frameworks for assembly languages; in particular, general syntaxes that can be applied across the board? There are, in fact, 3 in common use, which could each easily be adapted all CPUs - the Intel Syntax (which uses "DB"'s, "DS"'s, ";" to head line comments, ":" after labels), the Motorola Syntax (which uses "FCB"'s, "\*" to head line comments, strict formatting for labels and no ":") and the VAX Syntax (which has relative labels, e.g. "1f", "1b" and prefixes directives by dots), the last of which is what GAS uses.

We devised the CAS syntax, which has not (yet) been ported to a wide range of CPUs. It's closer to M4 in terms of directives (and may even be redesigned as a dialect of M4), uses C syntax for assembly-time expressions and operations and is free form (e.g. multiple statements per line permitted). Comments are headed by ";;" or "//" or may be in "/\* ... \*/" form, and it has the "1f" and "1b" relative labels of the VAX syntax).

On the *other* question that you're asking: why can't CPUs all agree to do the same things or things cut from the same cloth? The answer is simple: it's a free market, they're not supposed to.

The differences between CPUs involve matters that are critical to their design and intended uses! The 8051/2, for instance, has large numbers of bit-sized and byte-sized registers and register windows - very convenient for multi-threaded applications and run-time systems. This is something also common with RISC processors. The CPUs intended for desktops or laptops (like the x86 family) have narrow register sets (and a corresponding bottleneck). The addressing modes are different, some have the equivalent of C's \*a++ = b or \*a-- = b", for instance. Processors in the x86 family from the 80386 onward have a large infrastructure for handling virtual memory, caching, paging, for distinguishing between different levels of protection, while the 8086 and 80186 do not. The interrupt-handling for different CPUs is different. Some have fixed locations for interrupt handler functions, others have fixed locations only for the function pointers, while others have virtual or paged locations. The level of support by the CPU for "location-independent" programs varies significantly.

Even the instruction sets can have significant differences. A processor with bit-sized registers, for instance, doesn't need a zillion different conditional branch instructions, only a few. Those without bit-sized registers may, instead, have a version of the "compare" (CMP) and "test" (TST) operations, along with a large number of conditional branch instructions.

The destinations for goto's and jumps are addressed in different ways. Some use absolute addresses, some use paged addresses or virtual addresses.

If you're going to try and smoothe over all those differences, then you're mission-creeping assemblers into being compilers, no matter how you try to frame it. That's the fallacious route that so-called "high level assemblers" went down. If you're going to go that way, then you might as well just use a compiler equipped with the ability to inject in-line assembly and (ideally, especially for embedded systems) the ability to inject your own custom run-time system/kernel in place of the compiler's default cookie-cutter run-time system/kernel.
> 0 votes

---
Tags: programming-languages, computer-architecture
---


# Question
Title: Designing a context free grammar for a language
Design a grammar for the language

$$F = \\{x^a y^b zx^b y^a\mid a, b\geq 1\\}$$

I'm trying to get a stronger grasp of designing grammars for languages. A thorough explanation of how to design the grammar for this language would be very much appreciated.

# Answer
> -1 votes
The following is a context-free grammar to describe $F$:

$$S\to xS'y$$

$$ S'\to xS'y\mid yS^{''}x$$

$$S^{''}\to yS^{''}x\mid z$$

---
Tags: context-free
---


# Question
Title: What is the complexity of computing $C(n + m, m)$?
$C$ here represents combinations. $$ C(n + m, m) = \frac{(n + m)!}{n! m!} = \frac{(n + m) * (n + m - 1) * \ldots * (n + 1)}{m!} $$

In this formula it looks like it's $O(m)$ because both the numerator and denominator is $O(m)$, if I'm not mistaken.

Alternatively, $$ C(n + m, m) = \frac{(n + m)!}{n! m!} = \frac{(n + m) * (n + m - 1) * \ldots * (m + 1)}{n!} $$ In this formula it looks like it's $O(n)$ because both the numerator and denominator is $O(n)$, if I'm not mistaken.

So is the complexity $O(\min(n, m))$?

# Answer
> 3 votes
In the word RAM model, any pure function which takes a constant number of machine words and returns a constant number of machine words is assumed to cost $O(1)$ time. This is because any such function could, in principle, be implemented as a static memory lookup or a new CPU instruction.

If you're asking about the complexity of a specific algorithm, then analyse the algorithm, not the problem.

If you're asking about the case where $m$ or $n$ are *not* representable as a constant number of words (i.e. "big integers"), then neither algorithm that you presented is optimal for sufficiently large $m+n$. Remember that multiplication and division of large integers are not $O(1)$-time operations!

---
Tags: time-complexity
---


# Question
Title: Reading process memory of computer A on computer B?
So I was wondering if there is a way of reading process memory of one device on another. So lets say a process is running on computer A, I then use some form of connection lan, pcie etc. Once the two computers are connected. Would it be any way possible to then, say open something like cheat engine and read process memory of PC A on PC B in real time. Has something like this been done before/is possible?

# Answer
Yes. It is called RDMA and techniques like Infiniband rely on it.
> 1 votes

---
Tags: memory-hardware, memory-access
---


# Question
Title: Why is programmed I/O not suitable for high-speed data transfer?
I am learning about computer architecture and organization.

I have read that programmed I/O is not suitable for high-speed data transfer because it does not support synchronous mode of data transmission that is a requirement for many high-speed peripherals like disk.

But programmed I/O supports synchronous mode of data transfer. I am confused. Can someone please help me?

References: Assignment 10 question number 2

# Answer
There are 3 flavors of dealing with IO:

1. Programmed I/O (PIO). So for every 'data item', you need to execute an instruction on the CPU and the CPU will wait for the instruction to complete. So if you have a lot of data (so many 'data items') that needs to be send/received, the CPU will be blocked for a long time.
2. Interrupt driven I/O. So the transfer starts on the CPU, and on completion of the transfer, an interrupt is send. This means that the CPU is free for other tasks. But for every data item you still need to interact with the CPU. So better than #1, but still not great.
3. DMA: a DMA controller (either a central one or one on the storage device) will take care for sending multiple data items without any involvement of the CPU. So prevent the CPU from being a bottleneck.

I'm not sure if I'm understanding your question correctly. PIO is synchronous because the CPU is stalled.

There is another level where synchronous and asynchronous can be important. Modern interconnects like a link with PCIe is made of lanes and each lane is an asynchronous serial bus. The advantage of an asynchronous serial bus is that the source and destination are not limited by a common clock signal (hence the name asynchronous) and as a consequence can have very high bandwidths.
> 1 votes

# Answer
You can of course write a program which runs on a CPU and performs synchronous I/O.

But there are ways this can fail pretty easily: for example, your program may run on a pre-emptive operating system (i.e. all modern OSses like Linux and other Unices, Windows etc.) and simply not be scheduled quickly enough. Or, if your program manages to convince the OS to keep it scheduled, it may block other processes badly (e.g., if there is a GUI, it may freeze/stutter; or if there are other real time processes *they* might fail).

If you are in a setting without pre-emptive multitasking, i.e. on a microcontroller which you have under control yourself, then creating truly synchronous programs is still considerably harder than asynchronous. For slow protocols this wouldn't be an issue (you can simply rely on an interrupt timer, either on-chip or via some external circuit), but for very fast protocols you might need to fine-tune your algorithm to take the number of clock cycles of individual operations into account; and you probably will be hard pressed if you allow interrupt operations on the same uC.

Finally, a general purpose uC which is still fast enough for your high speed transfer after the above considerations might be exorbitantly more expensive than a dedicated separate chip.
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: Why has it taken so long to prove that P != NP?
A question that answers itself.

---

1. If P=NP could be proved in a formal language, then surely it would be as easy to verify the proof as it would be to discover/derive it? Couldn't a program just quickly check that every sentence/line obeyed the formal rules?
2. If P!=NP could be proved in a formal language, then it could take a while to do so.
3. Its taken a while to formally prove either P=NP or P!=NP.

-\> So either our language isn't accurate, isn't formal enough or P!=NP?

# Answer
> 2 votes
Suppose that $\mathsf{P}=\mathsf{NP}$. Your argument seems to be the following: since there exists an algorithm $A$ that is able to check whether a given **short proof** of mathematical statement is valid then there must exist an algorithm $B$ that decides whether such a short proof exists. Let's use $B$ on the statement $\mathsf{P}=\mathsf{NP}$.

There are several problems with that. First it assumes that $\mathsf{P}=\mathsf{NP}$ in the first place. If we knew that this is true we would have no need to run $B$ on $\mathsf{P}=\mathsf{NP}$.

Second, it assumes that we **know** $B$ while the above argument only shows that some $B$ must exist. It might be the case that $B$ exists but we don't know it. Moreover, if $B$ existed and we knew it, then $B$ itself would be a proof that $\mathsf{P}=\mathsf{NP}$.

Third: Suppose that $\mathsf{P}=\mathsf{NP}$ (but we don't know it) and that we have some magic *candidate* algorithm $B$. $B$ is only able to decide whether an input statement admits short proofs. By short I mean proofs whose lengths are upper bounded by $n^c$, where $n$ is the length of the statement, and $c$ is a constant of choice. How do you pick $c$? We don't know how long a proof of $\mathsf{P}=\mathsf{NP}$ is.

Finally, notice that $\mathsf{P}=\mathsf{NP}$ is a **specific** statement. Therefore, if we assume that "$\mathsf{P}=\mathsf{NP}$" can be proved either true or false, then we already have a **constant-time** algorithm that settles the matter. Consider the shortest proof written in binary (in some proof language) of "$\mathsf{P}=\mathsf{NP}$" or "$\mathsf{P} \neq \mathsf{NP}$" and let $k$ be its length. Clearly $k$ is a fixed number. We can simply generate all possible proofs in lexicographic order and check whether each of them is a valid proof of either "$\mathsf{P}=\mathsf{NP}$" or "$\mathsf{P} \neq \mathsf{NP}$". Eventually we will reach the proofs of length $k$. There are only finitely many proofs of length at most $k$ (namely $2^{k+1}-1$) and checking each of them requires a time upper bounded by some function $f(k)$. Therefore the overall running time is $O(2^k f(k)) = O(1)$. This constant can be **huge** and this does not bring us any closer to settling the $\mathsf{P}$ vs $\mathsf{NP}$ question.

# Answer
> 4 votes
Sometimes a short and easily verifiable proof takes a long time to discover. This may be due to several reasons. Maybe the general consensus in the research community is that the claim is probably not true, and most people who work on it are trying to prove the converse. Maybe it's believed to be too difficult for current techniques, and most researchers prefer to work on easier problems where progress can be made. Maybe finding it requires computer searches that were out of reach of older (or even current) hardware. Maybe it requires some radical new idea.

For a concrete example, take Kaplansky's unit conjecture. It claims that certain classes of generalized polynomials $K\[G\]$ do not contain nontrivial invertible elements. If this conjecture is false, then there exists such a class $K\[G\]$ and a nontrivial invertible polynomial $f \in K\[G\]$. If we are given this $K\[G\]$ and $f$, it's easy to verify (by computer or on paper) that it disproves the conjecture. The conjecture was stated in 1940 and publicized in the 1950s, and a counterexample was found by Gardam in 2021 using a computer search. He has stated that it ran on his laptop, so it probably would have been in reach of much earlier supercomputers.

Then there's the possibility that $P = NP$ is provably true, but its simplest proof is very long and difficult. Maybe there is a polynomial time algorithm for Boolean satisfiability, but it's extremely intricate and has a running time of $n^{10000}$ or something even more outrageous.

# Answer
> 0 votes
It's important to address the elephant in the room:

> Why has it taken so long to prove that P != NP?

This has *not* been proven.

The argument you have given "does not compute" - it uses terms that simply do not find together.

The one (the question of whether $P$ equals $NP$) and the other (the difficulty of finding a proof for it or its opposite) has nothing to do with each other whatsoever. Since the $O$ notation removes all multiplicative and additive constants, there can be P problems which are arbitrarily difficult to solve, so you can never use the perceived difficulty in finding a solution/proof to argue whether a problem is in $P$ or $NP$, both or none. As a fun example, by some definitions chess is an $O(1)$ problem in $P$.

---
Tags: complexity-theory, computational-linguistics, philosophy
---


# Question
Title: Merging all adjacent and overlapping rectangles in a grid to bigger rectangles
I have a × rectangular grid of cells, and a set of rectangles within this grid. Each rectangle is a subset of the cells. (Alternatively, you can think of them as axis-aligned rectangles where each of the four corners has integer coordinates.) Some of these rectangles overlap and some of these rectangles are adjacent. I want to merge adjacent rectangles to bigger rectangles if possible and remove overlaps.

So my output set should have bigger non overlapping rectangles instead of small adjacent or overlapping rectangles. The number of rectangles in the output set should be minimized. The output set need not be a subset of input set. Is there any approximate or exact algorithm for this problem?

# Answer
> 3 votes
Take a look at this paper. You can interpret each coordinate pair in your grid that is part of at least one input rectangle as being part of a polygon $P$, and every coordinate pair that does not belong to any input rectangles as not being part of $P$.

Then the problem becomes partitioning $P$ into the smallest number of non-overlapping rectangles. The referenced paper provides a polynomial-time algorithm.

Interestingly, the problem becomes $\mathsf{NP}$-hard when the output rectangles are allowed to overlap. See the discussion in this paper and the references therein.

---
Tags: algorithms, computational-geometry
---


title: SUBSET SUM reduction to PARTITION

text:
# Question
Title: SUBSET SUM reduction to PARTITION
This is the PARTITION problem:

> Given a multiset S of positive integers, decide if it can be partitioned into two equal-sum subsets.

This is the SUBSET SUM problem:

> Given a multiset S of integers and an integer T, decide if any subset of S sums to T.

The positive variant of `SUBSET SUM` is NP-complete.

---

`SUBSET SUM` can be reduced to `PARTITION` as follows:

Define `S' = S + {c}`, where `c = 2T - sum(S)`. `S'` can be partitioned into two equal-sum subsets iff there is a subset in `S` summing to `T`.

---

Proof:

Partition `S` into `A` and `B`:

`S = A + B`

If there exists a subset in `S` summing to `T`, then `S` can be partitioned so either `sum(A) = T` or `sum(B) = T`. Suppose `sum(A) = T`. Let `S' = A + B'` where `B' = B + {c}`.

```
sum(B') = sum(S) - sum(A) + c
sum(B') = sum(S) - sum(A) + 2T - sum(S)
sum(B') = -sum(A) + 2T

```

By assumption, `T = sum(A)` therefore `sum(B') = sum(A)`. This means `S'` can be partitioned into two equal-sum subsets.

If there does not exist a subset in `S` summing to `T`, then there cannot exist a `c` such that `S'` can be partitioned into two equal-sum subsets.

Suppose for contradiction `c` can exist.

Adding `c` to `B` creates `S' = A + B'`.

What value of `T` produces `c` such that `sum(A) = sum(B') = sum(B) + c`?

```
sum(A) = sum(B) + c
sum(A) = sum(B) + 2T - sum(S)
sum(A) = sum(B) + 2T - (sum(A) + sum(B))
sum(A) = sum(B) + 2T - sum(A) - sum(B)
2sum(A) = 2T
sum(A) = T

```

But `A` already sums to `sum(A)`, contradicting the assumption that there is no subset of `S` summing to `T`.

---

If `2T < sum(S)`, then `c < 0`, but PARTITION only applies for positive integer multisets. Does this reduction still hold?

# Answer
You should make $c=|2T-sum(S)|$. Show that the reduction then holds no matter what $T$ is.
> 0 votes

---
Tags: reductions, np-hard, partitions, subset-sum
---


title: comparision based sorting algorithms

text:
# Question
Title: comparision based sorting algorithms
The book CLRS says that any comparision sort algorithm requires omega(nlgn) comparisions n the worst case. My question is that why for heapsort it's O(nlgn) not omega(nlgn) since heapsort is also a comparision based algorithm?

# Answer
> 2 votes
Comparison based sorting algorithms require $\Omega(n \log n)$ comparison (notice the *big* omega).

Heapsort uses $O(n \log n)$ comparisons. This is not a contradiction since $\Omega(n \log n) \cap O(n \log n) \neq \emptyset$, i.e., there are functions of $n$ that are both in $\Omega(n \log n)$ and in $O(n \log n)$.

To be more precise, all comparison-based algorithms must use $$ \log\_2 n! \ge \log\_2(n^n e^{-n}) = n\log n - n \log\_2 e $$ comparisons, while Heapsort uses at least $n \log n - n \log\_2 e$ comparisons (since it is a comparison-based sorting algorithm) and at most $c n \log n$ comparisons for some fixed constant $c\>0$.

---
Tags: sorting
---


# Question
Title: Can the "closest neighbor" algorithm get arbitrarily bad in TSP?
Let's consider the following simple algorithm for attacking the Travelling Salesman Problem:

> Choose the pair of cities $(A,B)$ where $A\neq B$ and the distance between $A, B$ is minimal amongst all the distances of the cities. Start with $A$, then visit $B$, then in each step visit the nearest city not visited already, until there is no more city left.

Given $k\in \mathbb{N}$, is there a setting of cities such that the total distance travelled is more than $k$ times the distance travelled in an optimal solution?

# Answer
> 2 votes
Consider an instance with $4$ cities $a, b, c, d$ and the following distances: $d(a,b)=1$, $d(a,c)=d(b,c)=2$, $d(a,d) = d(b,d) = 3$, $d(c,d) = M$ for some $M\>3$.

Your algorithm visits the cities in one of the following two orders: $$ \langle a,b,c,d \rangle \quad \mbox{or} \quad \langle b,a, c, d\rangle. $$

In any case the cost of the tour is at least $d(c,d) = M$, while the tour $\langle a, d, b, c \rangle$ has cost at most $3 + 3 + 2 +2 = 10$. This shows that the solution returned by your algorithm can be at least $\frac{M}{10}$ times more costly than an optimal tour. Pick $M$ as large as you desire, e.g. $M=10k+1$.

Theorem 2 in this paper shows that the approximation ratio of the nearest neighbor algorithm can be $\Omega(\log n)$, where $n$ is the number of cities, even when distances satisfy the triangle inequality

---
Tags: traveling-salesman
---


# Question
Title: Can a computer determine whether a mathematical statement is true or not?
I was reading *Introduction to the Theory of Computation* by *Michael Sipser* and I found the following paragraph quite interesting:

> During the first half of the twentieth century, mathematicians such as Kurt Godel, Alan Turing, and Alonzo Church discovered that certain basic problems ¨ cannot be solved by computers. One example of this phenomenon is the problem of determining whether a mathematical statement is true or false. This task is the bread and butter of mathematicians. It seems like a natural for solution by computer because it lies strictly within the realm of mathematics. But no computer algorithm can perform this task. Among the consequences of this profound result was the development of ideas concerning theoretical models of computers that eventually would help lead to the construction of actual computers

As a CS student, completely new to the theory of computation, this is hard to believe for me. It said that a computer can't solve a basic task such as determining whether a mathematical statement is true or false. Can't it really!? I have programmed lots of codes that determine if a mathematical statement is true or not. For example, a simple code such as `return 6 == 2*3` will return true if this statement is true, so why does the text says that a computer can't perform this task?

I'm sure I'm missing something here. Perhaps I'm mistaken by the definition of "Mathematical statement". But I'm quite sure "Is 6 equal to 2 * 3?" is a mathematical statement and can be validated by a computer. So what did the text mean by that? I'm confused!

PS: Sorry if the Complexity theory tag is misplaced here. As I said I'm new to the field and on the same page the author of the book stated that the theories of computability and complexity are closely related.

# Answer
> 76 votes
The claim is not that a computer cannot determine the validity of *some* mathematical statements. Rather, the claim is that there is a class $\mathcal{C}$ of mathematical statements such that no algorithm can decide, given a statement from class $\mathcal{C}$, whether it is valid or not.

The standard choice for the class $\mathcal{C}$ is statements about natural numbers, for example:

> Every even integer greater than two is a sum of two primes.

The class $\mathcal{C}$ contains all statements of the form:

> For all natural $n\_1$ there exists natural $n\_2$ such that for all natural $n\_3$ there exists natural $n\_4$ such that ... there exists natural $n\_{2m}$ such that $P(n\_1,\ldots,n\_{2m})$,

where $P$ is an expression using logical operators, comparison operators, addition, subtraction, multiplication, division, and integer constants.

Another popular choice for the class $\mathcal{C}$ is:

> The following algorithm halts: ...

In both cases, there is no algorithm that takes an arbitrary statement from class $\mathcal{C}$ and correctly outputs whether the statement is valid or not.

---

It is crucial that the algorithm be required to answer correctly for *all* statements in $\mathcal{C}$. We can easily write an algorithm that answers correctly on a *single* statement from $\mathcal{C}$. Indeed, one of the following algorithms will work:

> The statement is valid.

> The statement is not valid.

Similarly, we can design an algorithm that answers correctly on *two* different statements $A,B$. One of the following will work:

> The statement is valid.

> The statement is not valid.

> If the statement is $A$, then it is valid, otherwise it is not valid.

> If the statement is $B$, then it is valid, otherwise it is not valid.

We cannot implement this strategy in the case of infinitely many statements, since an algorithm, by definition, has a finite description. This is the hard part – being able to decide, for *infinitely many* statements, whether they are valid or not.

# Answer
> 31 votes
On top of what everyone else has said, it may be worth talking about where some of the boundaries of decidability and undecidability are.

For natural numbers:

* The first-order theory of natural numbers with only addition (Presburger arithmetic) is *decidable*.
* The first-order theory of natural numbers with only multiplication (Skolem arithmetic) is *decidable*.
* The first-order theory of natural numbers with addition and multiplication (Robinson arithmetic; this is very close to Peano arithmetic without induction) is *undecidable*.

For real numbers:

* The first-order theory of real numbers with addition, subtraction, multiplication, and division (real closed fields) is *decidable*.
* The first-order theory of real numbers with addition, subtraction, multiplication, division, and the sine function is *undecidable*. This is one of the extensions of Richardson's theorem.
* Decidabiility of the first-order theory of real numbers with addition, subtraction, multiplication, division, and the exponential function is *unknown*. This is Tarski's exponential function problem, and it is one of the great unsolved problems in computability theory.

# Answer
> 15 votes
The key is quantifiers, both in the theorem, and in the "mathematical statements."

First, the theorem says that "there is no algorithm that can take in an arbitrary mathematical statement and prove if it is true or false." This does not mean that, for every mathematical statement, a computer can't determine if it's true or false. It just means that there's no computer program that will work on *all* mathematical statements.

The second relevant detail is that the mathematical statements they're talking about include quantifiers, For example, questions of the form "does there exist a number such that" or "does this hold for all numbers." Essentially, the intuition is that there's no way to know when you're done searching. If you're looking for a number with a given property, when do you stop? You can look at each number in sequence, but if none satisfy the property, you'll keep checking numbers forever.

As a concrete example of this, nobody currently knows whether the Collatz conjecture is true. Either there is some number that makes the Collatz sequence continue without a 1, or there is no such number. But there's no way to ask a computer whether such a number exists, since we wouldn't know when to stop looking. So, we have no idea.

In the absence of quantifiers, most mathematical statements about (computable) operations on numbers are easy: just evaluate the left hand side, evaluate the right hand side, and see if they're the same. But this is a very restricted subset of the questions that are interesting in math.

# Answer
> 9 votes
The statement is overly broad, as well as being overly complimentary to people. Computers can’t solve all problems but neither can people. Not sure why the extra drama was added.

What that is referring to is basically an aspect of the Halting Problem. A Turing machine can determine the answer to some questions but is unable to do so for others. They even mention Turing/Church.

# Answer
> 6 votes
A simple example of undecidable mathematical statements are whether multivariate integer polynomials have natural roots.

This means that we an expression $E(n\_0,\ldots,n\_k)$ built from natural number constants, natural number variables $n\_0,\ldots,n\_k$, addition, substraction and multiplication. We then want to know whether a solution for $E(n\_0,\ldots,n\_k) = 0$ exists.

A computer can in principle find a solution if there is one, just by exhaustively searching through all candidates, plugging them in and evaluating the expression. However, there is no general procedure to rule out the existence of a solution.

Further reading: https://en.wikipedia.org/wiki/Diophantine\_set

# Answer
> 5 votes
What you're misunderstanding is how "problem" is used in computer science. "Problem" does not refer to finding the correct output for a particular input, but writing an algorithm that returns the correct output for all inputs. For instance, is there an algorithm that sorts a list in linear time? You could write a program that simply goes through the inputs and checks whether it's already sorted, and if so, returns that input, and that would constitute "an algorithm that can sort a list in linear time" for some interpretation of the phrase, but it's not a solution to the problem of linear sort, because a linear sorting algorithm has to be capable of sorting *any* list. So when they say "One example of this phenomenon is the problem of determining whether a mathematical statement is true or false", they mean "One example of this phenomenon is the problem of writing a program that determines, for all mathematical statement, whether that statement is true or false."

The reason we can't do this is because computer science is a subset of mathematics. Any computer science question can be put in terms of mathematics. Given a mathematical statement and a program, "the program will say that the statement is true" can itself be expressed as a mathematical statement. What the work of Godel, Turing, and Church shows is that given any program, it's possible to construct a mathematical statement such that the statement claims that the program will say that it's false. That is, given a program P, it's possible to define a statement S such that S = "Program P will say that Statement S is false". So if P does in fact say that S is false, then S is true, so P was wrong. But if P says S is true, then S is false, so P was wrong. P can't possibly return a correct response. It's like asking someone "Are you going to answer 'no' to this question?" Whether they say 'yes' or 'no', they're wrong.

This argument only applies once we create statements that are complicated enough to talk about themselves. It doesn't say that programs can't evaluate simpler statements, such as `6 == 2*3`.

# Answer
> 3 votes
Other people have covered explaining the actual meaning of the theory this paragraph referenced. I will instead address how the quoted paragraph was intended to be interpreted, such that it does in fact correctly describe the theory.

> During the first half of the twentieth century, mathematicians such as Kurt Godel, Alan Turing, and Alonzo Church discovered that certain basic problems ¨ cannot be solved by computers. One example of this phenomenon is the problem of determining whether a mathematical statement is true or false.

The crucial point for this segment is that "a mathematical statement" is not referring to any particular specific statement, nor even to a not-yet-specified statement. "A mathematical statement" is describing an input to the problem, that may be given any arbitrary value that matches the description, and truly solving the problem requires specifying a solution that will work for every conceivable possible value of that input.

> This task is the bread and butter of mathematicians. It seems like a natural for solution by computer because it lies strictly within the realm of mathematics. But no computer algorithm can perform this task.

This segment confusingly uses the phrase "this task" to mean different things in different places, only one of which actually matches the problem described immediately before it.

The task of determining whether an individual specific mathematical statement is true or false is indeed the bread and butter of mathematicians, and that application of the problem to individual input values is what the first use of "this task" refers to.

The other use of "this task" refers to the general case I described above, of solving the problem for every conceivable input value, so that your solution is guaranteed to produce a correct answer no matter what input value you apply it to.

The general case task is impossible for computers, and it is also impossible for mathematicians. In fact, it's simply impossible, period. *That* result, the fact that the general case cannot be completely solved by any means, is the really remarkable thing about this.

> Among the consequences of this profound result was the development of ideas concerning theoretical models of computers that eventually would help lead to the construction of actual computers

This section is going off on another topic, irrelevant to understanding the issue asked about here.

# Answer
> 3 votes
The computability-based generalized incompleteness theorem with its proof would shed more light on your question. In particular, Yuval's answer states but does not prove that the set of true arithmetical sentences (true according to the standard model $(ℕ,0,1,+,·)$ of PA) is undecidable. The linked post shows via reduction to the halting problem that the set of sentences about whether a specified program halts on a specified input is undecidable, and every such sentence can be expressed as an arithmetical sentence.

Note that the linked post also explains why the crux for undecidability is in fact not really about having the ability to reason about both addition and multiplication, contrary to what some people might think after seeing that both Presburger arithmetic and Skolem arithmetic are decidable. That actually is an artifact of arithmetic, not undecidability! To see why, note that TC (a simple finite axiomatization of finite binary strings with just concatenation, as mentioned in the linked post) is essentially incomplete; there is no program that decides whether a sentence over TC is a theorem of TC or not.

The crux of incompleteness is actually nothing more than the ability to reason about finite program execution, and Godel's crucial contribution was to show that PA can do this. Turing noticed that if we ignore the encoding issue, the crux is that the halting problem is undecidable by a program. The encoding issue (which is the actually hard part of Godel's work) is in fact a distraction from the core of incompleteness, which you can see from the case of TC.

In fact, Dan Willard designed a theory that can reason about enough arithmetic and yet can prove its own consistency, and the trick was simply to axiomatize subtraction and division instead of addition and multiplication, to evade the unbounded generation property that is one key ingredient of the ability to reason about finite program execution. See this post for more philosophical stuff related to this unboundedness issue.

# Answer
> 2 votes
I find postings above saying a computer can decide the truth or falsity of some statements but not of some others.

I find that a somewhat misleading way of putting it. For statements in first-order logic, a computer can search for a proof and if one exists it will find it. But if the program has been running for a trillion years and hasn't yet found a proof, there is no way to know whether that's because no proof exists or the search hasn't gone on long enough. This was proved in the 1930s.

# Answer
> 1 votes
So, Captain Kirk tells the android that Harry Mudd is a liar. Everything he says is a lie. The android accepts this premise, whereupon Harry Mudd says, "I am lying." The android expresses confusion that Mudd cannot be lying b/c that would be true and that cannot be true b/c he is a liar. Smoke comes out of his ears and Kirk saves the day! This is Star Trek.

You ask a question famous enough to have a name, "The Halting Problem."

Kurt Goedel shook the foundations of mathematics by formulated a theorem equivalent to "This theorem cannot be proven." He thus demonstrated any interesting axiomatic system could not be complete (including Mudd-like theorems) and consistent (including provably false theorems).

Apply this thinking to the Halting Problem. Suppose you had a program that proves theorems in an axiomatic system. Now construct a Muddy theorem therein and hand it to the program. If it halts, it's verified a falsehood. If it doesn't, the program hasn't done its job.

This is an old enough result that the people who thought of it performed computations using rooms full of people with a job title of "computer." The bosses would like to know when they could send folks home and how much overtime they'd have to pay... This paradox is even older than that b/c the Apostle Paul writes in Titus 1:12 'One of Crete's own prophets has said it: "Cretans are always liars, evil brutes, lazy gluttons."'

Douglas Hofstadter has written this much better than I in his book Gödel, Escher, Bach: an Eternal Golden Braid,

# Answer
> 1 votes
Interesting question.

The sentence is: determining whether **a mathematical statement is true or false**

1 - There are plenty of mathematical statements which could easily be decided right or wrong as you have depicted using 2\*3=6 example. Hence making a general rule using the phrase -a mathematical statement- is startling, since it simply implies **"any problem"**. Even though it is said in the previous sentence that "...**certain basic problems** cannot be solved...", but it is still ambiguous and mind boggling. So I should give it to you. In my humble opinion, the sentence is wrong as a general rule which makes you right. (don't panic, keep reading)

2 - When one reads through the introduction, the assumption is, one is not properly familiar with the true meaning behind terms like "problem classes" and "degree of complexity" and omitting those terms makes it very uneasy to demonstrate the very correct notion behind such an advanced scientific fact. (look at what you get in the accepted answer: ...there is a class *C* of mathematical statements such that...).

# Answer
> 0 votes
You can write a computer program that will prove / disprove some mathematical theorems. There are some problems that can be solved very easily but need an enormous number of steps to solve; computers can handle them easier than humans. For example the statement “1526753673279839 is a prime” is no big deal for a computer.

But there are two problems. One is there are many statements that are in principle impossible to prove true or false. Humans can’t solve them, and computers can’t. Can’t solve them now, and won’t be able to solve them ever.

The other more interesting (in my opinion) problem is that writing a program that can prove difficult theorems is very, very difficult. Proving Fermat's Last Theorem was really, really hard. I’d bet that writing a computer program that could do this would be ten times harder. Not impossible, but really hard.

Wiles needed an awful lot of intuition for his proof, and intuition is just “anything that we have no idea how to turn into an algorithm”. Not impossible, but we have no idea.

PS. I’m not talking about hypotheticals. When I say “a program that can solve FLT” I mean that in the sense that every sensible person would mean it, that is a program that can run on a reasonable computer in a human’s lifetime and produce a result.

PPS. Why do I find it a lot more interesting to look at how to write software that can prove provable theorems? Because unsolvable problems have been examined years ago, and mostly we only look at them because a new generation of new students arrives. All you need to know about them can be found on this single webpage, and read in an hour.

But actually proving theorems, that is both possible and very, very hard. Just try writing a program that can solve the Intermediate Value Theorem. Make it understand what a continuous function is. What a compact set is. What real numbers are. And then let it come up with the idea that the supremum axiom can be used. And of course you can't prove a theorem by producing ten to the gazillionth power of logical conclusions, because you don't have enough time to do it, you can't represent the proof if you found it, and it can't be verified.

(One class of proofs that hasn't been mentioned: Proofs that can be quite short but are practically impossible to find. There's a nice theorem: For every prime p, there is a proof that p is prime which can be checked in polynomial time. But that proof can be very hard to find!)

---
Tags: complexity-theory, computability
---


# Question
Title: What is the nature of the two bits of data held in a computer memory cell?
I hope this question doesn't offend anyone. I start off by saying that I have and always had difficulty understand the language used in computer science so I have to interpret everything into the language of physics of electronics.

First what is termed as memory, I seem to think that it refers to energy that is held basically in one of two forms, either in an electric field or a magnetic field. And what is referred to a memory cell is the mechanism ( a physical thing) that this field is held. I have noticed that for all practical purposes memory/energy is held in an electric field.

It appears to me what is called a memory cell is made of two physical mechanism, a capacitor that the electric field is contained and a transistor to access the memory, i.e. the energy held in that electric field of the capacitor.

What is termed as word-line seem to refer to the conductor that goes to the gate of the transistor, and what is termed as bit line is a connection to the Drain part of the transistor. And the capacitor that the energy is held is connected to the Source part of the transistor.

Furthermore, it appears that the word-line is a way to access the energy while the bit line does two things, in-put and out-put. I seem to interpret the input as charging the capacitor and the output is when the charge is released back, accessed, coming back from the capacitor.

If I had all that correct only then my question perhaps have meaning otherwise it can not be answered. I had to describe all the above just to save a whole lot of back and forth and the effort for someone else to explain the details in language I won't understand. This of course I assume that what I have described in itself understandable in the first place even if it is false, that is.

Since in computer language information/memory/data is represented in binary, i.e. 0 and 1.

My question is: Does 1 ( in computer language) means that the capacitor is charged? Does the 0 mean that the capacitor is discharged, meaning it is dead, like a dead battery?

Or Does 1 mean that the capacitor is charged with some higher voltage value? And the 0 mean that the capacitor is charged in some lower voltage value?

I can understand the 1 to mean some voltage value. But I can not understand the capacitor being dead, fully discharged as to mean 0.

Why do I have difficulty with the 0 interepetation of a dead no voltage capacitor? Because in the particular memory cell, the presence of a capacitor would be meaningless. And I should say that I specifically am referring this to what is termed as paramenent memory that is established in the factory, not-erasabale or rewritable.

Furthermore an obsence of voltage, or 0 is already the case by default. In other words if there is nothing to read, it then has to be interepreted as reading "nothing to read". Or when programming a 0, it would mean you don't do anything to the particular cell as it is in a discharged state by default.

And one more question which is the right thing to do. When a permanent memory is accessed ( i.e. read) the capacitor is discharged, the bit line having a larger value voltage due the discharge of the capacitor. Now this discharge state of the capacitor can not remain as it does not have infinite charge. It has to be recharged immediately and this can only be done by the same bit line ( as write). Is this correct? Furthermore this must be the value 1, bit 1. And if the particular cell is value of 0, there is nothing to read or write and by default that cell is interpreted as 0 as no voltage is there in the bit line as reading and no current will be sent as input/writing.

I am sorry, that I have typed so much and have not kept my question direct and simple. I have only done with genuine intention to save the headache tring to explain and make their answer easier for them.

So brief and to the point now: Does 1 represent presence of voltage or some higher voltage? Does 0 represent no voltage or some lower voltage but voltage nontheless? Does ROM ( factory non-writeable, no-erasable, non-changeabale) cell needs to be charged to retain its factory setting? In a floating gate transistor cell ( looking at the diagram) in what part of that gate, electric field is held, (if the floating gate itself is made of two membrane or...)? Thank you.

# Answer
At a very low level, a hardware designer will decide what means 1 and what means 0. For example, they might say "Anything above 3.7V means 1, and anything below 1.9V means 0, and any voltage in between should be avoided and shouldn't happen.

And then they design a NAND gate with three inputs and say "If all three inputs are above 3.7V then the output will be 0.5V, but if any input is below 1.9V then the output will be 4.5V. If any inputs are between 1.9V and 3.7V then no guarantee what the output is".

And above that level, we can completely forget about the hardware level.
> 1 votes

---
Tags: memory-hardware, memory-access, encoding-scheme, binary
---


# Question
Title: Cache coherence is worthless and does nothing?
When you perform a write on a multi-cpu system, relevant cache flushes are done to ensure that the other cpus see the change immediately.

**BUT**

That write was issued from an independent thread on a preempting operating system, so there never was any expectation that it would arrive at any particular time. All that cache coherency achieves is to change the 'no particular time' of the data's arrival to a slightly different 'no particular time'. How is that of even the slightest value ?

# Answer
It is false to assume that a write to a cache-line will cause a flush to main memory. Caches on modern CPUs are always coherent. Modern caches are also write behind caches meaning that in theory they never need to write to main memory. The primary reasons for a cache-line to end up at main memory are:

* lack of space in the cache.
* limitation in the cache coherence algorithm. E.g. with MESI if a different CPU wants to read a dirty cache-line, the cache-line needs to be written to main memory to prevent the change being lost. MOESI solves this problem.
* I/O DMA.

Cache coherence provides 'coherence':

1. a total order over all loads and stores on a single address.
2. a read needs to see the most recent write before it this order.

In very simple terms: cache coherence provides sequential consistency per address.

An example test for #1:

```
initial state:
   a=0

CPU1:
   a=1
CPU2:
   a=2
CPU3:
   r1=a
   r2=a
CPU4:
   r3=a
   r4=a

```

Can it be that r1=1, r2=2, r3=2, r4=1 (so CPU3 saw the changes in different order than CPU4). No. this is not allowed.

An example test for #2:

```
initial state:
   a=0

cpu1:
   a=1
cpu2:
   r1=a
   r2=a

```

Can it be that r1=1 and r2=0? So are you allowed to see a 'stale' value once you read a newer value? No, this can't happen because once you see 1, you can't go back in time and see the value before it.

Coherence is the key to understand any memory model. If you don't understand coherence, everything you build on top remains fragile. In almost all modern processors (GPU is the only exception I know of) caches are always coherent.

For an excellent read on the topic, see A primer on memory consistency and cache coherence second edition.. The book can be downloaded for free which is pretty amazing seen the quality of the book.
> 5 votes

# Answer
Cache coherency protocols (generally) do not enforce *time*, they enforce *order*.

There is an essential (i.e. non-removable) race condition if two CPUs try to write to the same cache line at the same time. One of them will win and one of them will lose. That doesn't matter as long as all CPUs see them as happening in *the same order*. And if it does matter, that's a concurrency bug in the program.

Memory barriers also enforce order, not time. Think about what must happen when a CPU releases a lock: all writes in the critical section must occur *before* the write that releases the lock. This is an ordering constraint, not a time constraint.
> 4 votes

# Answer
Consider implementing a mutex. A mutex is either locked or unlocked. If it is locked by another processor, you can't lock it. If two processors try to lock a mutex at exactly the same time, one "wins" and locks the mutex and owns the mutex, and one "loses" and doesn't own the mutex.

There's no guarantee which processor wins if they both try at the same time. But cache coherency can make sure that *one* wins and *one* loses and both know who is the winner and who is the loser. Without that, implementing a mutex that works correctly 100% of the time and not 99.999999% of the time would be very, very hard.

And pveentjer's link looks very good.
> 1 votes

---
Tags: computer-architecture, concurrency
---


# Question
Title: Given graph $G=(V,E)$ and weight function $w\,:\,E\to\mathbb{N}$, function $f(G,w)$ finds the heaviest clique in the graph, prove $L(M)=CLIQUE$
Given graph $G=(V,E)$ and weight function $w\\,:\\,E\to\mathbb{N}$, function $f(G,w)$ finds the heaviest clique in the graph, when the sum of a clique is the sum of the weights on all of the edges.

I want to prove that there is a Turing machine $M$ so I will get $L(M)=CLIQUE$, using function $f$, where $CLIQUE$ is the language of all $(G,k)$ so $G$ has a clique of size $k$.

I wrote the following algorithm:

> $M$ on $(G,k)$:
>
> 1. Build a weight function $w$ so each edge in $G$ gets $1$.
> 2. Calculate $f(G,w)$.
> 3. Accepts if and only if $f(G,w)\geq k$.

My professor noted that it should be $f(G,w)\geq {k \choose 2}$. Is it possible to explain why?

# Answer
A clique $C$ on $k$ vertices has $\binom{k}{2}$ edges, i.e., all unordered pairs $\\{a,b\\}$ such that $a$ and $b$ are distinct vertices in $C$.

The number of such pairs is $\frac{k (k-1)}{2} = \binom{k}{2}$. You can count these by focusing on the number of *ordered* pairs first. To make an ordered pair $(a,b)$ you have $k$ choices for $a$ and $k-1$ choice for $b$ (i.e., all vertices in $C$ except for $a$). The number of ordered pairs is then $k(k-1)$. To get the number of *unordered* pairs you only need to divide the above quantity by $2$ since, for each unordered pair $\\{a,b\\}$, we counted both $(a,b)$ and $(b,a)$.
> 2 votes

---
Tags: graphs, np, clique
---


# Question
Title: Nearest neighbor algorithm for TSP when triangle inequality holds
The output given by this nearest neighbor algorithm for the Travelling Salesman Problem can be arbitrarily bad. In the example constructed here, the triangle inequality doesn't hold in most cases.

Let $L$ be the set of positive real numbers $r\in\mathbb{R}\_+$ such that for every setting of TSP such that the triangle equality holds, we have that the length of the tour that the nearest neighbor algorithm gives is at most $r\cdot \ell$, where $\ell$ is the optimal (minimal) length of any tour.

**Question.** Is $L$ non-empty? If yes, what is $\inf L$?

# Answer
The set $L$ is empty.

Theorem 2 in this paper shows that, for any integer $m \> 3$, there exists an instance with $n = 2^m - 1$ cities such that **it satisfies the triangle inequality** and the approximation ratio of the nearest neighbor algorithm on this instance is larger than $\frac{\log(n+1)}{3}$.

Pick your favorite $x \in \mathbb{R}\_+$, and choose $m= 4\lceil x \rceil$. By the above theorem, the approximation ratio must be larger than $\frac{\log(n+1)}{3} = \frac{\log 2^m}{3} = \frac{m}{3} \> x$. This shows that $x \not\in L$.

(All logarithms are in base 2)
> 1 votes

---
Tags: traveling-salesman
---


# Question
Title: How to know if language is in comp or np?
I'm new to the site.

I had a test a few days ago and failed it, I had a question I did not understand.

This is the question:

Let's look at the *FALSE* language: Collect all the verses *P* in the form of CNF so that any placement on the variables *P* will not satisfy *P*. We will mark the number of variables in *N* and the number of verses in *M*. Determine which of the following statements is correct:

1. The language is in P. You can build an algorithm running in time O (max{N^5, M\*N}^2)
2. The language is in NP.
3. The language is in CONP.

How do I know what the correct answer to the question is? How can I tell if the FALSE language belongs to np or conp I do not understand.

# Answer
> 1 votes
I assume that by "verses" you mean boolean formulas.

The language is definitely in CO-NP since a "no" certificate is a satisfying assignment.

Currently we don't know whether FALSE is in P nor whether it is in NP.

---
Tags: complexity-theory, time-complexity, computability, reductions, np
---


# Question
Title: Examples of higher order algorithms ($\mathcal{O}(n^4)$ or larger)
In most computer science cirriculums, students only get to see algorithms that run in very lower time complexities. For example these generally are

1. Constant time $\mathcal{O}(1)$: Ex sum of first $n$ numbers
2. Logarithmic time $\mathcal{O}(\log n)$: Ex binary searching a sorted list
3. Linear time $\mathcal{O}(n)$: Ex Searching an unsorted list
4. LogLinear time $\mathcal{O}(n\log n)$: Ex Merge Sort
5. Quadratic time $\mathcal{O}(n^2)$: Ex Bubble/Insertion/Selection Sort
6. (Rarely) Cubic time $\mathcal{O}(n^3)$: Ex Gaussian Elimination of a Matrix

However it can be shown that $$ \mathcal{O}(1)\subset \mathcal{O}(\log n)\subset \ldots \subset \mathcal{O}(n^3)\subset \mathcal{O}(n^4)\subset\mathcal{O}(n^5)\subset\ldots\subset \mathcal{O}(n^k)\subset\ldots $$

so it would be expected that there would be more well known problems that are in higher order time complexity classes, such as $\mathcal{O}(n^8)$.

What are some examples of algorithms that fall into these classes $\mathcal{O}(n^k)$ where $k\geq 4$?

# Answer
Brute-force algorithms can be considered as a good example to achieve the mentioned running times (i.e. $\Omega(n^4)$).

> Suppose given the sequence $\sigma=\langle a\_1,a\_2,\dots , a\_n\rangle$ of real numbers, you want to find, if exists $k$ elements ($k\geq 4$, and $k$ is constant ) from $\sigma$ such that $$\sum\_{i=1}^{k}a\_i=0.$$

Obviously, a simple brute-force algorithm for this problem check all $\binom{n}{k}$ subsets of the input and detect whether the elements in at least one of them sum to $0$. If $k$ is a constant then $\binom{n}{k}=\Theta(n^k)$. For example if $k=10$ then the running time of your algorithm is $\Theta(n^{10}).$ Finally, you find algorithm for your desired running time.
> 3 votes

# Answer
The problem of $1$-processor gap scheduling of $n$ jobs has time complexity $O(n^7)$.

The paper is available here.
> 2 votes

# Answer
Most simple example gives nested cycles: we know that, if we want, for example, find similar elements for 2 arrays, then we used 2 nested loops and therefore we have $O(n^2)$ complexity.

Hence, every 4 nested loops gives complexity $O(n^4)$, $k$ nested loops $O(n^k)$.

Another examples Karmarkar's algorithm, AKS primality test
> 1 votes

---
Tags: time-complexity, p-vs-np
---


# Question
Title: How many /20-subnets are in the network 130.149.0.0/16?
I'm new to networking so please bear with me. My textbook gives 4 as an answer, but I'm not sure I understand the question:

1. What's a "/20-subnet"? My understanding is that a network mask (/20) is used to give structure to a classless IP-address, i.e provide a way to distinguish network bits from host bits. In this case the network mask is 11111111.11111111.11110000.00000000, so we could use 12 bits for hosts and subnets.
2. Why should a network address (in this case 130.149.0.0) have a mask? We know that the last 16 bits are 0's and can be used for hosts and subnets. What does the mask (/16) mean here?

I'm not sure how they arrived at the solution (4 bits). Can you please explain this to me?

# Answer
A network mask of /16 means that $16$ of the $32$ bits (since we are using IPv4) are the common prefix used for the network, while the remaining $32-16=16$ (least-significant) bits are used to address to hosts in the network. This allows for $2^{16}$ different host addresses.

Similarly, a network mask of /20 fixes the first $20$ bits and leaves $30-20=12$ bits for the hosts in the subnetwork. This allows for $2^{12}$ addresses in the subnetwork.

Since we had $2^{20}$ addresses available in our /20 network, we can only create $\frac{2^{16}}{2^{12}} = 2^4 = 16$ subnetworks with netmask /16.

Alternatively you can arrive at the answer as follows: we have $16$ free bits to address to hosts in our network but we are allocating the $12$ least significant bits to the host of our subnetworks. This leaves us $16-12=4$ bits to address our subnetworks. With $4$ bits we can create $2^{4}=16$ distinct subnetworks.

An IP address as such does not need to have a mask. If you also specify a mask you are adding more information than the simple address: you are also splitting the address space into the network prefix and the host identifier. In your case the notation 130.149.0.0/16 is not representing the address of a single host but rather the addresses allocated to network. This is telling you that (i) the first 16 bits are part of the network prefix, and (ii) these bits are exactly those represented by the two octets 130 and 149 (here 16 is a multiple of 8 so the prefix is exactly an even number of octets).
> 0 votes

---
Tags: computer-networks, ip
---


# Question
Title: Complexity of `n & (n - 1)` should be O(1) or O(log n)?
I'm looking at the methods posted in https://www.geeksforgeeks.org/program-to-find-whether-a-no-is-power-of-two/ for checking whether `n` is a power of 2.

Method 5, pasted below, in the link claims to be O(1) but shouldn't it be O(log n)? When we do `n & (n - 1)`, that's a bitwise operation over 32 bits (since `n` is a 32 bit integer), right?

```
bool isPowerOfTwo (int x)
{
    /* First x in the below expression is for the case when x is 0 */
    return x && (!(x&(x-1)));
}

```

Method 2, pasted below, claims to be O(log n), which I am not sure if it's correct either. The number of while loops is O(log n) and each while loop iteration is O(log n) (because we're bitwise-and'ing log n bits), so shouldn't it be O(log^2 n)?

```
bool isPowerOfTwo(int n)
{
    if (n == 0)
        return 0;
    while (n != 1)
    {
        if (n%2 != 0)
            return 0;
        n = n/2;
    }
    return 1;
}

```

I always get a bit confused with complexity analysis on the bit-scale.

# Answer
In the RAM model with uniform costs and word size $\Omega(\log n)$ the first algorithm requires $O(1)$ time since each word operation takes constant time.

The second algorithm requires time $O(\log n)$ since each iteration can be performed in $O(1)$ time and there are at most $O(\log n)$ iterations (after each iteration the value of $n$ is at most half the previous value).

If you want to use logarithmic cost model, then the first algorithm takes linear time in the number of bits of $n$, i.e., $O( \log n)$ time. The second algorithm (as written) takes $O(\log n)$ time per iteration to perform the comparison and to shift all the bits towards the right (this is the `n=n/2` operation). The number of iterations is $O(\log n)$ as before. The overall running time is $O(\log^2 n)$.

All running times in this answer are tight (in the sense that if I said that an algorithm requires $O(f(n))$ time then there is a suitable infinite family of inputs that cause the algorithm to require $\Omega(f(n))$ time).
> 2 votes

# Answer
Well, in theory the first one is $O(\log n)$. In practice, if $n \< 2^{64}$ for example, it is a fixed number of operations on a 64 bit processor. Likely to cost 1 or at most 2 nanoseconds. (And I would write it as (x & (x-1)) == 0 && x != 0, so the comparison x != 0 isn't done for all numbers, but only for numbers that are either powers of two or equal to 0). If n can be large, say 100s of bits, then for every 64 bit in n you have the same cost again.

And in theory, the second one is $O(\log^2 n)$, while in practice it is $O(\log n)$. Same reasoning.
> 0 votes

---
Tags: time-complexity, bit-manipulation
---


# Question
Title: SAT algorithm for determining if a graph is disjoint
What are some good algorithms to have a SAT (CNF) solver determine if a given graph is fully-connected or disjoint?

The best one I can think of is this:

* Number the nodes 1..N, where N is the number of nodes in the graph.
* define N^2 variables with the ordered pair (P, Q), where P = 1..N and Q = 0..N-1.
* Set (1,0) to true.
* Set (A,P+1) to true iff there is an edge connecting node A and node B and (B,P) is true.
* If there exists a true (X,Y) variable for all possible nodes X, then the graph is connected.

Effectively, (X,Y) means "Node X is Y steps away from node X".

This seems inefficient at O(N^2) variables. Can this be improved?

A comment (from when I posted this on cstheory.stackexchange.com) asked why I would need a SAT-based algorithm when O(N) algorithms for connectivity are well-known. The reason is simple -- I have many other SAT-based constraints on the graph that also need to be satisfied at the same time.

# Answer
> 9 votes
Given a graph $G = (V,E)$, here is a SAT instance which is satisfiable iff the graph is not connected.

Pick an arbitrary vertex $v\_0 \in V$, and add the following clauses, over the variables $x\_v$ for $v \in V$:

* $x\_{v\_0}$.
* For every $(u,v) \in E$, $\lnot x\_u \lor x\_v$ and $\lnot x\_v \lor x\_u$.
* $\bigvee\_{v \neq v\_0} \lnot x\_v$.

Here is a SAT instance which is satisfiable iff the graph is connected.

Pick an arbitrary vertex $v\_0 \in V$, and add the following clauses, over the variables $x\_{v,i}$ for $v \in V$ and $i \in \\{0,\ldots,n-1\\}$:

* $\lnot x\_{v,0}$ for all $v \neq v\_0$.
* For every vertex $v \in V$ and $i \in \\{0,\ldots,n-2\\}$, $\lnot x\_{v,i+1} \lor x\_{v,i} \lor \bigvee\_{u\colon (u,v) \in E} x\_{u,i}$.
* For every vertex $v \in V$, $x\_{v,n-1}$.

# Answer
> 5 votes
Yuval describes a boolean CNF formula that is satisfiable iff the graph is not connected, using $|V|$ variables; and a boolean CNF formula that is satisfiable iff the graph is connected, using $|V|^2$ variables.

I describe here a boolean CNF formula that is satisfiable iff the graph is connected, using $O(|V| \lg |V| + |E|)$ variables. If $|V|$ is large enough and the graph is sparse, this is better than Yuval's solution.

Introduce variables $d\_v$, one for each vertex $v \in V$, over the domain $d\_v \in \\{0,1,\dots,|V|-1\\}$, and variables $y\_{u,v}$, one for each edge $(u,v) \in E$. Add the following constraints:

* $d\_{v\_0} = 0$
* $d\_v \le d\_u + 1$ for each $(u,v) \in E$
* for each $v$, there exists $u$ such that $(u,v) \in E$ and $y\_{u,v}$
* $y\_{u,v} \implies d\_v = d\_u + 1$

Here the intended interpretation of $d\_v$ is that it captures the distance (length of the shortest path) from $v\_0$ to $v$; and the intended interpretation of $y\_{u,v}$ is that it should be true if the edge $(u,v)$ is part of a shortest path $v\_0 \leadsto v$. Note that this system of constraints has a satisfying assignment iff the graph is connected.

Now you can convert this to SAT using "bit-blasting". In particular, for each $d\_v$, introduce variables $x\_{v,i}$ for $i=0,1,\dots,\lceil \lg |V| \rceil -1$; the intended meaning is that $x\_{v,i}$ is the $i$th bit of $d\_v$. Now we can express the constraint $d\_v \le d\_u+1$ using $O(\lg |V|)$ additional variables and clauses (e.g., by building a circuit for this comparison and using Tseitin's transform). Also, we can express the constraint "for each $v$, there exists $u$ such that..." using $|V|$ clauses, one for each $v$, each of which is a disjunction over the appropriate set of $u$. In this way, we obtain a set of CNF clauses that uses $O(|V| \lg |V|)$ variables for the bit-blasting of the $d$'s, and $|E|$ variables for the $y$'s. This yields a CNF formula as claimed above.

---
Tags: graphs, satisfiability, constraint-satisfaction
---


# Question
Title: SAT formula for connected graphs on the grid
In the answer to an earlier question "SAT algorithm for determining if a graph is disjoint" a formula is constructed that is satisfiable iff a given graph is connected.

The formula uses a lot of variables, as basically a breadth first search is performed and the variables code the number of steps needed to reach a vertex from the origin (which is an arbitrary, fixed vertex).

Here I want to specialise this to graphs that are actually embedded on the grid. The vertices are the points of a $m\times n$ grid, and edges are only between the east/north/west/south neighbours in the grid.

Is there a solution that is more variable-efficient, using the restricted topology?

# Answer
I added a new answer, https://cs.stackexchange.com/a/142450/755, to that question. Applied to your situation, my solution uses $O(mn \lg(m+n))$ variables, which is asymptotically better than Yuval's algorithm (which uses $mn(m+n)$ variables).
> 0 votes

---
Tags: satisfiability, square-grid, connected
---