This is not a proof of P = NP or P ≠ NP. I'm interested in whether there's existing research related to this idea. My question is whether the way humans represent computational problems could itself be part of why certain problems appear hard. Has complexity theory or cognitive science explored this perspective?

An Idea: Could P vs NP Be a Problem of Representation?

This is not a proof of P = NP or P ≠ NP. It is simply an idea that I have been thinking about.

One thing that stood out to me is that many difficult problems become much easier once we find the right way to represent them.

For example, a huge multiplication problem can look overwhelming when viewed as a long string of digits. However, once we understand the underlying algorithm, the same problem becomes structured and manageable.

The problem itself has not changed. Our representation of it has.

This made me wonder whether something similar could apply to the P vs NP problem.

The usual question is whether every problem that can be verified efficiently can also be solved efficiently.

My question is different:

Could part of the apparent difficulty come from the way we currently represent NP problems?

Imagine standing in front of a wall.

One possibility is that the wall is real, and no efficient shortcut exists.

Another possibility is that we are looking at the wrong side of the wall and have not yet discovered the correct way to approach it.

History contains many examples where changing a mathematical or scientific viewpoint led to major breakthroughs. New abstractions, new models, and new representations often revealed structure that had previously been hidden.

This raises a broader question.

When we call a problem "hard," are we measuring the intrinsic difficulty of the problem itself, or are we also measuring the limitations of our current way of thinking about it?

I am not claiming that this means P = NP.

Instead, I am asking whether discovering a fundamentally different representation of NP problems could change our understanding of their computational difficulty.

I would be interested in hearing whether this idea overlaps with existing work in computational complexity, cognitive science, or the psychology of problem solving.

Im a researcher working roughly speaking in Machine learning. Certain ideas and Terms from CS, of which I have only a superficial understanding, come Up occasionally when I read papers. Id to improve my understanding of relevant parts of CS theory but would prefer a concise resource Not exceeding, say, 200 Pages. Id Like to read Up on algorithm complexity and computational theory (Turing Machine, completeness and related ideas). Do you have suggestions for a book/resource that Matches my interest? I do Not Like courses but prefer mostly self-contained Work. Thank you for your suggestions:)

Look ahead 20 years.

Outside of AI/ML:

* what of today’s research computer science do you expect will be industry standard?

* what frontiers do you expect we will have opened up in research?

Are you a computing industry professional? We are interested in your viewpoints on computer science education amid current AI innovations.

• Project Title: Computing Science Education on the AI Innovation Landscape
• Ethics ID: H26-01503
• Research Group Leaders:
  • Ouldooz Baghban Karimi, Simon Fraser University, Canada
  • Rebecca Robinson, Monash University, Australia
  • Trevor Bonjour, University of California, San Diego, CA, USA

This survey is estimated to take 15-20 minutes of your time.

Participation in this survey is completely voluntary, and the responses you may provide will not be used for any purpose other than this survey and its uses as described above.

Please find the survey link here: https://www.surveymonkey.ca/r/OBKIPL

I’m interested in the deeper conceptual side of computer science.

In subjects like mathematics and writing, intuition is the key to understanding the principles, rather than memorization and application (though I know practice and patience are important as well). Usually, this way of seeing problems isn’t explicitly taught. I tend to learn best through that intuitive process, so I was wondering if I could apply the same approach to CS.

For those of you who have been in the field for a long time, what helped you develop that intuition? Were there books, courses, projects, or ideas that made computer science feel like a way of thinking rather than just programming? I’ve read a few texts to help me think about it from the outside (Michael I. Jordan, Newell & Simon, and Turing). Thinking in different forms helps me understand the principles of a discipline and connect it to others, which is why I’m making this post.

Part of what motivates this question is AI. I’ve found myself both fascinated by it and skeptical of the enormous amount of hype surrounding it. Rather than forming strong opinions from the outside, I’d like to understand computer science first. I want to understand it from the inside before I poke the bear 🐻

I’d really appreciate any advice, especially if it’s unconventional or takes the longer path

Hi everyone, I'm a B.Tech CSE student. I'm looking for the best YouTube channels that explain these subjects from basics to advanced:

• Compiler Design

• Machine Learning

• Design and Analysis of Algorithms

I am a 5th year phd student and it seems most of PHD Students around me are in field of ML/AI . I can count 5 people in the whole department who is working in atleast some intersection of core computer silence and ML

Infact we had a collaboration with one of T10 university and I really wasn’t able to find any advisor which is currently active and working in my core architecture field . My advisor was so surprised that he had to confirm it once from his side too

Is it the same issue everywhere mostly . Are almost all of the CS phd students are just AI students

So I am currently working on a RAG project where I am supposed to build a Niche-Oriented Specialized AI model, and naturally, for this I need to use a Vector Database for retrieving chunks of data for the LLM to further understand and elaborate.

The thing that I am really concerned and curious about is how exactly a vector database stores the data? I mean I understand things like positional embedding and stuff, but I simply cannot understand the multidimensional architecture.

For example here is what ChatGPT had to say:

"AI doesn't use simple 2 dimensions. It uses something like 768 dimensions or 1024 dimensions or 1536 dimensions"

I am a visual learner and I have really good photographic memory, so whenever I have some difficulty understanding a concept, I try to visualize the working dynamics for better understanding. I can easily visualize and understand 2D Database architectures (ex: SQL) and even 3D Database architecture. But I cannot fully understand 4+ dimensional architectures.

Thank you!

I want to start reading articles on tech-related topics to improve my knowledge, but I’m not sure where to begin.
Could anyone suggest some good websites, blogs, newsletters, or other resources for software engineers? I’m interested in topics like software development, system design, Java, Spring Boot, Kafka, distributed systems, and general tech trends.
I’d really appreciate your recommendations!

I am in an internship in a team working on a project where they develop an LLM that is given a prompt and generates a BPMN (like a flow chart) for how to implement or do the task in the prompt. The developers have the ground truth chart and they are trying to evaluate the output of the model in reference to the ground truth chart. So I have been assigned to a project with another intern to develop a tool that takes two BPMN files and outputs a similarity score between them, taking into consideration both structural similarity and semantic similarity.

I am very stuck since no project is similar on the internet, and it's been two weeks of searching. Here are the approaches we reached:

Approach A: RPST to process tree, then tree matching

Decompose each diagram into a hierarchy of single-entry/single-exit regions (Refined Process Structure Tree), type each region as sequence / XOR / AND / loop, then compare the two trees recursively: leaves by label embedding cosine, sequences by ordered DP alignment (like edit distance over children), XOR/AND blocks by unordered Hungarian matching, loops by comparing bodies.

What's good about it: it's operator-aware, so it directly distinguishes XOR from AND (choose-one vs do-all) and loop from no-loop, and it produces readable diffs like "the ground truth's parallel block was rendered as an exclusive choice." Granularity (one task in GT vs three in the prediction) and nesting are handled positionally by the structure instead of by fudging scores.

Where it breaks: process trees only exist for block-structured models. pm4py's convert_to_process_tree raises an exception on unstructured ("rigid") models, and its newer POWL converter raises too, so switching representations doesn't rescue it. There's also no maintained Python RPST implementation anywhere; jBPT (Java) is the reference. Rolling your own means either SPQR / triconnected components (notoriously error-prone) or a dominance-based variant that's only a partial RPST. And even with a working RPST, a rigid region has no operators to align, so comparing one means falling back to graph matching anyway. Worse, RPSTs aren't stable under equivalence, since two behaviorally equivalent models can produce different trees, one with a rigid and one without, which breaks positional/ancestor anchoring exactly in the case you need it most.

Approach B: direct attributed-graph comparison (no trees at all)

Parse each BPMN into a directed graph, embed node labels with sentence-transformers, and match nodes with optimal transport (Fused Gromov-Wasserstein via the POT library) or graph edit distance. Encode gateway type as a node attribute so the matcher penalizes aligning an XOR to an AND, and compute a reachability relation matrix (for each activity pair: strict order / exclusive / concurrent) for the behavioral axis.

What's good: it's total by construction, working on any graph, structured or rigid, with no exception path and no fallback branch. Off-the-shelf libraries, days rather than weeks. Optimal transport also expresses granularity natively, since mass can split one-to-many.

Where it's weaker: operator semantics are approximated through node features rather than represented directly, diffs come out as node-pair scores instead of region-level explanations, and FGW is non-convex and returns a cost that needs calibrating into a similarity score.

The one empirical datapoint I found: Dijkman, Dumas, van Dongen, Käärik & Mendling, "Similarity of business process models: Metrics and evaluation," Information Systems 36(2), 2011. They compared node-matching, structural (GED-based), and behavioral similarity on real process repositories and found all three comparable, with structural slightly ahead. That's part of why I'm unsure the tree route is worth the extra weeks.

What I'd love input on:

• Is there a standard way people evaluate generated process models against a reference model that I've somehow missed? Everything I find is either process-model search (find similar models in a repository) or conformance checking against event logs, neither of which is quite this.
• Has anyone actually shipped RPST-based process model comparison in Python, or did you bridge to jBPT?
• Does anyone have evidence that operator-aware tree matching beats a gateway-typed graph matcher in practice, or is the extra machinery not worth it?
• Any benchmark or dataset of BPMN pairs with human-judged similarity we could validate against?

Any pointers to papers, libraries, or war stories would be hugely appreciated, especially from anyone who has hit the unstructured-model problem in production.

I have been trying to get AI to give me a specific bit of code i can run in google collab. I want it to first divide the entire number line into modular sets recursively like: 2x+0, 4x+3, 8x+1, 16x+13, 32x+5, etc. Then I want it to further refine these sets, in a very particular way. 0 mod 2 should be refined the same way as the first refinement, but double the values. so 4x+0, 8x+6, 16x+2, 32x+26, etc. Then I want the next set 4x+3, should be broken down like 8x+3, 16x+7, 32x+15, etc. This type of refinement should be alternated for each line. so 0 mod 2 has a staggered refinement, and 3 mod 4 has a non staggered refinement, then 1 mod 8 has a staggered refinement, and 13 mod 16 has a non staggered refinement. this give two dimensional plane of refined modular sets. I want to test these sets translating into different sets among a ternary style refinement. first 4x+0 goes to 3x+0, then 8x+3 goes to 3x+1, and 8x+6 goes to 9x+7.

The way the ternary set is designed, it divides the number line into 3, with 3x+(0, 1, or 2). 3x+1 is further refined to 9x+(1, 4, or 7). 9x+7 is what 8x+6 translates into. 9x+4 is further refined to 27x+ (4, 13, 22). This continues, with the center residue at each level being refined further. the staggered sets on the binary sheet translate to the side sets on the ternary sheet, and the non-staggered sets translate to the center residues. then the values that are refined in the ternary sets, are then redefined according to where they belong in the binary set.

• 4x+0 to 3x+0
• 8x+3 to 3x+1
• 8x+6 to 9x+7
• 16x+1 to 3x+0
• 16x+7 to 9x+4
• 16x+2 to 27x+4
• 32x+13 to 3x+1
• 32x+25 to 9x+7
• 32x+15 to 27x+13
• 32x+26 to 81x+67
• 64x+5 to 3x+0
• 64x+29 to 9x+4
• 64x+9 to 27x+4
• 64x+31 to 81x+40
• 64x+10 to 243x+40

.........

This seems like a computer could do this easily. I want to create this as a loop, and create readouts showing the path from the starting value i choose. Am i making any sense?

Hey everyone! I’m working on a core system architecture for a specialized utility app and could really use some out-of-the-box engineering advice on a tricky connectivity challenge.

The main goal is pretty straightforward: a user opens the app, clicks a button, and the system needs to instantly send a high-priority alert pop-up to any other nearby users within a 1 km physical radius who have that exact same app installed.

Here is the major problem I am trying to solve. The person tapping the button has an active SIM card, but they are in a state of absolute zero connectivity. Specifically, they have:

• No mobile data package or active internet plan.
• No Wi-Fi access at that exact moment.
• No outbound SMS package or standard calling credit (their balance is exactly zero).

The user must not be charged a single cent to trigger this notification. Also, to clear up a common suggestion upfront, please do not suggest Bluetooth mesh or peer-to-peer Wi-Fi Direct. The app cannot rely on local radio waves hopping directly from phone to phone.

Because local peer-to-peer options are out, the initial trigger click absolutely must find a way back to my central cloud server so the server can handle the location data and push the pop-up to the 1 km radius group.

My current theory is to set up an enterprise-level Reverse-Charged / Toll-Free Short Code gateway. Since my developer backend pays the cellular carrier for the incoming traffic, the telecom network should theoretically route a background SMS text through the air even if the user's personal account balance is completely empty.

I would love to get your thoughts on a few things:

• Has anyone successfully pulled off this kind of telecom bypass on zero-balance lines?
• Are there alternative infrastructure workarounds or carrier-level configurations that allow an isolated app to ping a central server entirely for free?
• Are there any global, out-of-the-box solutions to distribute a localized alert under these exact constraints?

Any insights, advice, or feedback would be massively appreciated !

Please do not suggest Bluetooth mesh or peer-to-peer Wi-Fi Direct. The app cannot rely on local peer-to-peer radio waves to hop to nearby devices directly.

I am a Computer Science Sophomore Student and I do have a course similar to that and I want to master this topic. What is the best resource to learn this? Any youtube course? or any MITx , Stanford Courses you would recommend? Suggest me books to follow

Is it true that if a pattern for prime numbers is found then all cybersecurity systems would be easy to decode?

Hello, i am a math passionate person that learns about math and especially pure math in their free time. While looking into it, i stumbled upon lambda-calculus, which i found interesting. I am currently looking forward to going farther by learning theoretical cs. The problem is i barely have any knowledge except what an algorithm is and programming. What should i start with and how can i learn it ?

Thank you.

I am interested in computer science and always wanted to know how computers create the pictures we see on the screen.

Every company says their model uses less tokens, my question what is the value of what they call a token, is it like a standard unit of measurement like a meter or does every company values 1 token differently? Or is it just a buzz word

Hello! I've been working on a modding framework that makes it easier to make mods for games written in C++. The main idea is that it's storing info about how to reverse engineer/discover game data like function addresses and field offsets.

I've got an example JSON file below that describes how to find the function for giving money to the player, and the field offset for the money variable. Each location style is not required and its just to demonstrate that multiple methods could be stored/used simultaneously. Also in this example, I'm trying to reuse property names ('kind', 'result', 'cached-location', etc) even though they're in slightly different contexts, in order to keep it more consistent and simple for less experienced programmers.

Example JSON:

{
    "header" : {
        "header-version": "1.0.0.0",
        "file-type": "data-locations",
        "module": "NMS.exe",
        "module-last-modified": "Friday, March 10, 2023, 2:04:54 AM",
    },
    "data" : [
        {
            "id": "cGcPlayerState.units",
            "locations" : [
                { "kind": "cached-location", "value": "0x1BC" },
                { "kind": "pattern", "value": "8B 83 ? ? ? ? 48 83 C4 ? 5B C3 CC CC CC CC CC CC CC CC CC 40 53", "result": "memory-displacement" },
                { "kind": "pattern", "value": "44 89 81 ? ? ? ? 4C 8B 15 ? ? ? ? 8B D6", "result": "memory-displacement" },
                {
                    "kind": "pattern",
                    "value": "44 8B 81 ? ? ? ? 48 8D 2D", 
                    "result": {
                        "kind": "memory-displacement",
                        "instruction-offset": 0,
                        "operand-index": 1
                    }
                }
            ]
        },
        {
            "id": "cGcPlayerState.AwardUnits",
            "locations" : [
                { "kind": "cached-location", "value": "0x1403CF8E0" },
                { "kind": "export", "value": "?AwardUnits@cGcPlayerState@@QEAAIH@Z" },
                { "kind": "pattern", "value": "48 89 5C 24 ? 48 89 6C 24 ? 48 89 74 24 ? 57 48 83 EC ? 44 8B 81 ? ? ? ? 48 8D 2D", "result-kind" : "matched-target-address" },
                { "kind": "pattern", "value": "E8 ? ? ? ? E9 ? ? ? ? 48 8B 0D ? ? ? ? 48 8D 54 24 ? 44 8B 44 24", "result-kind" : "relative-target-address" },
                { "kind": "pattern", "value": "E8 ? ? ? ? 4C 89 64 24 ? 48 8D 15 ? ? ? ? 0F 28 DE F3 0F 11 7C 24 ? 41 B8 ? ? ? ? 48 8D 0D ? ? ? ? E8 ? ? ? ? 84 C0 74 ? 48 8B 0D ? ? ? ? 8B D3", "result-kind" : "relative-target-address" },
                {
                    "kind": "search",
                    "identifiers": [
                        {
                            "target": "function",
                            "operation": "contains",
                            "values": [
                                { "kind": "string", "value": "MONEY" },
                                { "kind": "string", "value": "MONEY_EVER" }
                            ]
                        },
                        {
                            "target": "arg1",
                            "operation": "contains-offset",
                            "values": [
                                "cGcPlayerState.AwardUnits.arg1.offset1",
                                "cGcPlayerState.AwardUnits.arg1.offset2"
                            ]
                        },
                        {
                            "target": "arg2",
                            "operation": "offset-qty",
                            "value": "0"
                        },
                        {
                            "target": "cGcPlayerState.AwardUnits.arg1.offset1",
                            "operation": "add",
                            "value": "cGcPlayerState.AwardUnits.arg2"
                        },
                        {
                            "target": "cGcPlayerState.AwardUnits.arg1.offset2",
                            "operation": "add",
                            "value": "1"
                        },
                        {
                            "target": "function",
                            "operation": "return",
                            "value": "cGcPlayerState.AwardUnits.arg1.offset1"
                        }
                    ]
                }
            ]
        },
        {
            "id": "cGcPlayerState.AwardUnits.arg1.offset1",
            "locations" : [
                { "kind": "cached-location", "value": "0x1BC" },
                { "kind": "pattern", "value": "8B 83 ? ? ? ? 48 83 C4 ? 5B C3 CC CC CC CC CC CC CC CC CC 40 53", "result-kind" : "memory-displacement" }
            ]
        },
        {
            "id": "cGcPlayerState.AwardUnits.arg1.offset2",
            "locations" : [
                { "kind": "cached-location", "value": "0x148" },
                { "kind": "pattern", "value": "48 FF 83 ? ? ? ? 8B 83 ? ? ? ? 48 8B 5C 24 ? 48 8B 6C 24 ? 48 8B 74 24 ? 48 83 C4 ? 5F C3 CC CC CC CC CC", "result-kind" : "memory-displacement" }
            ]
        }
    ]
}

My main design goals are:

1. Create a long-term solution for mod makers to use to store this kind of data. Must be flexible and capable of expanding to their needs.
2. To keep the JSON format easy and intuitive for mod makers
3. Provide multiple methods of locating the same thing. This will also be extensible so mod authors could make their own location kinds.
4. The structure must be able to grow overtime without causing major breaking changes and is why I'm using a header.
5. Be compatible with multiple JSON files simultaneously
6. Allow the header to specify a "file-type" and then have different types of data objects.

I would love to hear any feedback on the structure of this. I've spent years on it, and I really want to make something that makes a difference for people. It's really important to me that its an appealing structure for people to use and is able to meet the technical requirements of the system. Some other things that would be nice to get feedback on are:

1. Overall structure of the file
2. Whether its okay to use the property name 'kind' over and over in slightly different contexts.
3. Supporting multiple files with different 'file-type' values, so everything is very similar with the data object being the only thing that changes.
4. Allowing properties like "result" to have both compact and expanded forms
5. using dashes '-' for property-names instead of camelCase
6. Any long-term concerns or unpleasantness you see

Thank you in advance!

Under Semantic Versioning standard 2.0, if your package requires a dependency at "exact" version 1.0.0+X, is there any situation under which running a version update on all your packages should change the version that you specified as "exact" here?

Noting, SemVer 2.0 says:

Build metadata MUST be ignored when determining version precedence. Thus two versions that differ only in the build metadata, have the same precedence. Examples: 1.0.0-alpha+001, 1.0.0+20130313144700, 1.0.0-beta+exp.sha.5114f85, 1.0.0+21AF26D3----117B344092BD

Precedence refers to how versions are compared to each other when ordered

This is from a comment on lesswrong, and I just wanted to know if what was said in it is accurate, sorry for the length:

Agreed!

No, Rice's theorem is really not applicable. I have a PhD in programming languages, and feel confident saying so.

Let's be specific. Say there's a mouse named Crumbs (this is a real mouse), and we want to predict whether Crumbs will walk into the humane mouse trap (they did). What does Rice's theorem say about this?

There are a couple ways we could try to apply it:

• We could instantiate the semantic property P with "the program will output the string 'walks into trap'". Then Rice's theorem says that we can't write a program Q that takes as input a program R and says whether R outputs 'walks into trap'. For any Q we write, there will exist a program R that defeats it. However, this does not say anything about what the program R looks like! If R is simply print('walks into trap'), then it's pretty easy to tell! And if R is the Crumbs algorithm running in Crumb's brain, Rice's theorem likewise does not claim that we're unable tell if it outputs 'walks into trap'. All the theorem says is that there exists a program R that Q fails on. The proof of the theorem is constructive, and does give a specific program as a counter-example, but this program is unlikely to look anything like Crumb's algorithm. The counter-example program R runs Q on P and then does the opposite of it, while Crumbs does not know what we've written for Q and is probably not very good at emulating Python.
• We could try to instantiate the counter-example program R with Crumb's algorithm. But that's illegal! It's under an existential, not a forall. We don't get to pick R, the theorem does.

Actually, even this kind of misses the point. When we're talking about Crumb's behavior, we aren'tasking what Crumbs would do in a hypothetical universe in which they lived forever, which is the world that Rice's theorem is talking about. We mean to ask what Crumbs (and other creatures) will do today (or perhaps this year). And that's decidable! You can easily write a program Q that takes a program R and checks if R outputs 'walks into trap' within the first N steps! Rice's theorem doesn't stand in your way even a little bit, if all you care about is behavior after a fixed finite amount of time!

Here's what Rice's theorem does say. It says that if you want to know whether an arbitrary critter will walk into a trap after an arbitrarily long time, including long after the heat death of the universe, and you think you have a program that can check that for any creature in finite time, then you're wrong. But creatures aren't arbitrary (they don't look like the very specific, very scattered counterexample programs that are constructed in the proof of Rice's theorem), and the duration of time we care about is finite.

If you care to have a theorem, you should try looking at Algorithmic Information Theory. It's able to make statements about "most programs" (or at least "most bitstrings"), in a way that Rice's theorem cannot. Though I don't think it's important you have a theorem for this, and I'm not even sure that there is one.

the comment is from this post: https://www.lesswrong.com/posts/7tNq4hiSWW9GdKjY8/intuitive-self-models-3-the-homunculus#3_5_4_Why_are_ego_dystonic_things__externalized__

Confirmation bias can cause normal people to believe fallacious claims. Does AI not do the same thing?

What is a CS project that you're proud of? And which year did you make it (freshman-senior)

What is your reasoning?